📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34830 🧐 관찰 및 접근 # 문제 상황을 차근차근 살펴보자 $a, b$가 있을 때, $a - b$ 를 한번 지나가면 된다. $a, b, c$가 있을 때, $a - b, b- c, c-a$를 한번씩 지나가야한다. $a, b,c ,d$가 있을 때, $a-b, a-c, a-d, b-c, b-d, c-d$를 한번씩 지나가야 한다. 이를 그래프 이론으로 해석할 수 있지 않을까? 그래프가 있고, 각 간선을 한번씩 지나되, 시점과 종점이 달라도 된다 한붓그리기가 가능한가? 이제 이 문제는 오일러 경로를 가능하게 하는 문제로 바뀐다. 오일러 경로는, 홀수점이 두개 이하일때 가능하다. 정점이 $N$개 있다고 하면, 그래프는 완전그래프이므로 각 정점에 붙어있는 간선은 $N-1$개이다. $N$이 홀수라면, 모든 $N$개의 정점은 짝수점이다. $N$이 짝수라면, 모든 $N$개의 정점은 홀수점이다. 따라서, $N-2$개의 점들을 연결해서 홀수점이 2개가 되도록 만드는것이 최적이다. 💻 풀이 # 코드 (C++): void solve(){ ll N; cin >> N; ll ans = N * (N-1) / 2; if(N%2 == 0) ans += N/2 - 1; cout << ans; }
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23086 🧐 관찰 및 접근 # 그래프와 간선이 주어졌을때, 특정 시점에 이분 그래프인가?를 찾는 문제이다. 이분그래프를 판정하는데에는 $O(N+M)$의 시간이 걸린다. 직관적으로 생각해보면, 리스트에 쓰인 차례대로 친한 친구를 절교시킬 수 있으므로, 리스트를 뒤집어서 하나씩 간선을 이어가며 해당 그래프가 이분 그래프인지 판정하는 방법을 쓸 수 있을 것이다. 이때 시간 복잡도는 $O(K(N+M))$이다. 이는 너무 느리다! 문제 상황을 조금 더 관찰해보자. $\text{ans}$개의 친한 친구 쌍을 절교시켜 이분 그래프가 성립하도록 했다면, $\text{ans}+1$개의 쌍을 절교시켰을때도 마찬가지로 이분그래프일 것이다. $0 \leq a \leq K$인 $a$에 대해, 이분그래프가 성립하는지는 단조성이 존재한다! **매개변수 탐색(파라메트릭 서치)**가 가능하다. 💻 풀이 # 코드 (C++): int N, M, K; vector<pair<int, int>> links[100010]; // (nxt, idx) vector<int> prohibit_list; int color[100010]; // 0: unvisited, 1: group A, 2: group B bool prohibited[200010]; bool isBipartite(int cnt){ rep(i, 1, M+1) prohibited[i] = false; rep(i, 0, cnt) prohibited[prohibit_list[i]] = true; rep(i, 1, N+1) color[i] = 0; rep(i, 1, N+1) if(color[i] == 0){ queue<int> Q; Q.push(i); color[i] = 1; while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto [nxt, idx]: links[cur]){ if(prohibited[idx]) continue; if(color[nxt] == 0){ color[nxt] = (color[cur] == 1 ? 2 : 1); Q.push(nxt); } else if(color[nxt] == color[cur]){ return false; } } } } return true; } void solve(){ cin >> N >> M >> K; rep(i, 1, M+1){ int u, v; cin >> u >> v; links[u].push_back({v, i}); links[v].push_back({u, i}); } rep(i, 0, K){ int p; cin >> p; prohibit_list.push_back(p); } // 모두 금지했을때 이분 그래프인가? if(!isBipartite(K)){ cout << -1; return; } // 파라메트릭 서치 int ok = K, ng = -1; while(ok - ng > 1){ int mid = (ok + ng) >> 1; if(isBipartite(mid)) ok = mid; else ng = mid; } cout << ok << "\n"; int groupA_sz = 0, groupB_sz = 0; isBipartite(ok); rep(i, 1, N+1) color[i] == 1 ? groupA_sz++ : groupB_sz++; cout << min(groupA_sz, groupB_sz) << ' ' << max(groupA_sz, groupB_sz) << "\n"; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2132 🧐 관찰 및 접근 # 트리에서 특정 경로 위에서 노드들의 가중치의 합 트리의 경로란, 하나의 간선을 두번 지나지 않으며 $a_i \in V, (a_i, a_{i+1}) \in E$ 를 만족하는 집합 다시말해, 그냥 특정 간선을 두번 타지 않고 갈 수 있는 시점~종점의 길 어떻게 구할지 생각해보자 어떤 점 $a_0$에서 경로를 시작한다고 해보자. 그 다음에 갈 수 있는 점은 $a_0$의 자식중 한곳에만 갈 수 있다. 한 자식한테 들어간다면, 다시 나올수가 없기 때문에 그 자식을 $a_1$이라고 한다면, 마찬가지로 그 자식중 한곳에만 갈 수 있다. 어? 이거 DFS아닌가? DFS처럼 할 수 있는 것 같다. 그러면 자식중에 어디로 가야하는가? 물론 가장 열매를 많이 먹을 수 있는 곳으로! 💻 풀이 # 코드 (C++): int N; vector<int> links[10010]; int val[10010]; int dfs(int cur, int par){ int ret = 0; for(auto nxt: links[cur]){ if(nxt == par) continue; ret = max(ret, dfs(nxt, cur)); } return ret + val[cur]; } void solve(){ cin >> N; rep(i, 1, N+1) cin >> val[i]; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } int ans = 0, idx = 1; rep(i, 1, N+1){ int res = dfs(i, -1); if(res > ans){ ans = res; idx = i; } } cout << ans << ' '<< idx << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32607 번역 흐로닝언 박물관 방문 문제 # 흐로닝언 박물관에서는 매일이 다릅니다. 어떤 날은 좋고 평화롭고 조용해서, 하루 종일 아름다운 그림, 조각, 그리고 다른 예술 작품들을 감상할 수 있습니다. 다른 날들은 더 바쁜데, 주말이나 공휴일에는 서두르는 방문객들, 높아진 입장료, 그리고 소리지르는 아이들로 박물관이 가득 찹니다. 이러한 불편함은 매우 다양합니다: 어떤 바쁜 날은 추가 학생 할인(studentenkorting) 덕분에 더 나을 수 있고, 어떤 조용한 날은 지진 위험 때문에 더 나빠질 수 있습니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/12858 🧐 관찰 및 접근 # $\text{gcd}(n, n+1)$은 몇일까? $G = gcd(n, n+1)$이 어떤 소수 $p$를 약수로 가진다고 하자. 이때 $p$는 간격 $p$마다 한개씩 존재한다. $p = 2$면 $p$를 약수로 가진 수는 $2$칸마다 존재한다. 따라서 연속된 두 수는 어떤 공약수인 소수 $p$를 가질 수 없다! 따라서 $\text{gcd}(n, n+1) = 1$임을 알 수 있다. 같은 방법으로, $\text{gcd}(a, b) = \text{gcd}(a, b-a)$ 임도 알 수 있다. 유클리드 호제법에서도 알 수 있듯이! 구간 쿼리지만, Lazy하게 연산하기는 쉽지 않아보인다. 하지만 $\text{gcd}(x_a, x_{a+1}, x_{a+2}, \dots, x_b)$ 를 $\text{gcd}(x_a, x_{a+2} - x_{a+1}, x_{a+3} - x_{a+2}, \dots, x_b - x_{b-1})$ 이라고 생각하면, 바뀌는 수는 생각보다 많지 않다! Lazy한 합 연산과 최대공약수에 대한 그냥 세그먼트 트리로 풀 수 있지 않을까? 사실 Lazy부분도 구간 덧셈, 점 쿼리이므로 그냥 세그로 바꿀 수 있지만, 귀찮으니까 ㅋㅋ 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; LazySegmentTree LST(N); ST.init(N-1); vector<ll> A(N); rep(i, 0, N) cin >> A[i]; rep(i, 0, N) LST.set(i, A[i]); LST.build(); rep(i, 0, N-1) ST.set(i, abs(A[i+1] - A[i])); ST.build(); int Q; cin >> Q; while(Q--){ ll op, a, b; cin >> op >> a >> b; a--; b--; if(op){ LST.update(a, b, op); if(a-1 >= 0) ST.update(a-1, abs(LST.query(a-1, a-1) - LST.query(a, a))); if(a+1 < N) ST.update(a, abs(LST.query(a+1, a+1) - LST.query(a, a))); }else{ cout << gcd(LST.query(a, a), ST.query(a, b-1)) << '\n'; } } } 🔒 구현 코드 잠금