최신 글
-
11505번: 구간 곱 구하기
11505번: 구간 곱 구하기사용 언어: C++ 풀이구간 합 구하기 문제와 유사. 구간의 곱을 구하는 것이므로 트리는 똑같이 만든다. 한 가지 다른 점은, 트리를 만들때 % MOD를 한다는 것인데, 어차피 마지막에 한번 Mod를 하나 중간 계속 Mod를 하나 결과는 같다. 그래서 Overflow가 안나게 매번 % MOD를 해준다는 것. Query에서도 곱을 하면서 % MOD를 해준다.#include using namespace std;typedef long long ll;const int MOD = 1'000'000'007;constexpr int SZ = 1 > N >> M >> K; for (int i = 0; i > num; Set(i, num); } for (int i..
-
2042번: 구간 합 구하기
2042번: 구간 합 구하기사용 언어: C++ 풀이리프 노드들은 입력 값들, 부모 노드들은 값들의 합으로 설정해서 O(log n)으로 구간의 합을 구하는 세그먼트 트리 문제다. 주의할 점은 a == 1일때 c가 int 범위를 넘어서 오버플로우가 발생할 수 있어서 long long을 설정해야한다.#include using namespace std;typedef long long ll;// SZ는 N보다 크거나 같은 2^k 꼴의 수 (2^20 == 1,048,576 > 1,000,000)constexpr int SZ = 1 > N >> M >> K; for (int i = 0; i > num; Set(i, num); // 세그먼트 트리 초기화 } for (int i = 0; i..
-
9372번: 상근이의 여행
9372번: 상근이의 여행사용 언어: C++ 풀이모든 도시는 연결되어있고, 현재 위치가 중요하지도 않으므로, 그냥 간선의 수 - 1이 답이다.#include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { int N, M; cin >> N >> M; for (int i = 0; i > a >> b; } // 모든 도시는 항상 연결되어있음 // -> 최소 간선 수는 항상 N-1 cout