제34회 한국정보올림피아드 (KOI 2017) 고등부 풀이

1. 물통 (bucket)

크기가 A인 물통과 크기가 B인 물통이 있고, 처음에는 모든 물통이 비어있다. 아래 4가지 동작을 통해 크기가 A인 물통에는 P 만큼, 크기가 B인 물통에는 Q 만큼의 물을 담는 최소 동작 횟수를 구하는 문제다.

1) 크기가 A인 물통을 비우거나 가득 채운다.

2) 크기가 B인 물통을 비우거나 가득 채운다.

3) 크기가 A인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 B인 물통이 가득 차면 옮기는 것을 멈춘다.

4) 크기가 B인 물통에 담긴 물을 크기가 B인 물통에 옮긴다. 이 때, 크기가 A인 물통이 가득 차면 옮기는 것을 멈춘다.

크기가 A인 물통에 a만큼의 물이, 크기가 B인 물통에 b만큼의 물이 담겨 있는 상태를 (a, b)라고 나타내자. 초기 상태나 위 4가지 동작 중 하나를 수행한 직후 다음과 같은 조건을 만족한다.

a=0 혹은 a=A 혹은 b=0 혹은 b=B

때문에 가능한 상태의 수는 $O(A+B)$라는 것을 알 수 있고, 이를 이용해 BFS를 통해 최소 동작 횟수를 구할 수 있다.

#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; int A, B, P, Q; int mem[100001][4]; struct Z{ int a, b; }; queue <Z> que; int& D(int a, int b) { if (!a) return mem[b][0]; if (a == A) return mem[b][1]; if (!b) return mem[a][2]; if (b == B) return mem[a][3]; return mem[0][2]; } void push(int a, int b, int d) { if (D(a, b) < 2e9) return; D(a, b) = d; que.push({a, b}); } int main() { cin >> A >> B >> P >> Q; for (int i=0;i<=B;i++) for (int j=0;j<4;j++) mem[i][j] = 2e9; push(0, 0, 0); while (!que.empty()){ Z q = que.front(); que.pop(); int a = q.a, b = q.b, d = D(a, b); push(0, b, d+1); push(a, 0, d+1); push(A, b, d+1); push(a, B, d+1); int v = min(A-a, b); push(a+v, b-v, d+1); v = min(a, B-b); push(a-v, b+v, d+1); } printf("%d\n", D(P, Q) < 2e9 ? D(P, Q) : -1); }

2. 문명 (civilization)

NxN 크기의 격자판에 초기 K개의 문명 발상지가 있다. 햇수가 지날수록 문명 발상지는 상하좌우로 인접한 칸에 문명을 전파시킨다. 이 때, 모든 문명이 하나로 결합될 때까지 걸리는 최소 햇수를 구하는 문제다.

이 문제를 Parametric search로 접근해서 결정 문제를 Flood-Fill로 해결할 경우 $O(N^2 \lg N)$ 시간복잡도를 가지며, 54점을 받는다.

이 문제를 $O(N^2 \alpha(n))$에 해결하기 위해서는 DSU(Disjoint Set Union, 서로소집합)을 이용하면 된다. 모든 문명이 하나로 결합된다는 것은 연결요소의 개수가 1개라는 것이고, Union-Find를 하면서 연결요소의 개수를 관리할 수 있기 때문에 연결요소의 개수가 1개가 되는 순간을 포착할 수 있다.

#include <bits/stdc++.h> using namespace std; int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}; int N, K, X, C; int D[2001][2001], num[2001][2001]; int par[2000*2000+9]; bool vis[2001][2001]; int find(int n){ return par[n] == n ? n : (par[n] = find(par[n])); } int main() { scanf("%d%d", &N, &K); for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) D[i][j] = 2e9, num[i][j] = ++X; for (int i=1;i<=X;i++) par[i] = i; queue <int> que; for (int i=1;i<=K;i++){ int r, c; scanf("%d%d", &r, &c); D[r][c] = 0; que.push(r); que.push(c); } int ans = 0; for (;;ans++){ while (!que.empty()){ int y = que.front(); que.pop(); int x = que.front(); que.pop(); if (D[y][x] != ans){ que.push(y); que.push(x); break; } vis[y][x] = 1; C++; for (int d=0;d<4;d++){ int ny = y+dy[d], nx = x+dx[d]; if (ny < 1 || ny > N || nx < 1 || nx > N) continue; if (vis[ny][nx]){ int a = find(num[ny][nx]), b = find(num[y][x]); if (a != b) C--; par[b] = a; }else if (D[ny][nx] == 2e9){ D[ny][nx] = D[y][x]+1; que.push(ny); que.push(nx); } } } if (C == 1) break; } printf("%d\n", ans); }

3. 요리 강좌 (cook)

N개의 학원 각각에서 M개의 강좌를 개설한다. 각 강좌는 순서대로 수강해야하고, 한 학원에서 연속해서 수강할 수 있는 강좌의 수는 최대 E개다. 그리고 S개 이상의 강좌를 연속해서 수강하면 학원을 옮길 수 있다. 그리고 학원을 옮길 때 비용 T 만큼을 지불해야한다. 마지막으로 각 학원마다 직전 강좌를 특정한 학원에서 수강한 학생을 받지 않는데, 이를 불허용 학원이라 한다. 각 학원마다 각 강좌를 수강하는데 필요한 비용이 주어졌을 때, 한 학생이 모든 강좌를 순서대로 수강하기 위해 필요한 최소 금액을 구하는 문제다.

다음과 같이 DP 배열을 정의한다:

D[i][j] = i번째 강좌까지 수강을 마친 상황이고 마지막으로 강좌를 수강한 학원이 j이며, 이제 막 학원을 옮기려고 할 때 필요한 최소 비용

그러면 점화식은 다음과 같다:

D[i][j] = min(D[k][l] + T + C[j][i] - C[j][k]) (단, S ≤ i-k ≤ E, l ≠ j, l ≠ j의 불허용 학원)

여기서 C[j][i] 는 학원 j에서 첫 강좌부터 i번째 강좌까지 수강했을데 필요한 비용 (즉, 누적합)

DP의 점화식을 보면, i-E이상 i-S이하인 k에 대해 j와 j의 불허용 학원 번호와 다른 모든 l에 대해 D[k][l]-S[j][k]의 최소값을 구하여 T + S[j][i]를 더해주면 D[i][j]가 된다라고 말할 수 있다. [i-E, i-S]라는 구간은 i가 증가할 수록 오른쪽으로 이동하고 l의 조건이 j와 다름,  j의 불허용 학원과 다름, 즉, 2가지라는 것을 고려할 때, N개의 deque와 각 k에 대해 D[k][l]의 최소값 상위 3개를 구해놓음으로써 이 문제를 $O(NM)$ 시간에 DP 배열의 값들을 계산할 수 있다.

DP 배열의 값들을 모두 계산한 뒤에, 답은 $O(NM)$ 시간복잡도로 naive하게 구할 수 있다.

#include <bits/stdc++.h> using namespace std; int N, M, S, E, T; int A[3001][3001], B[3001]; int D[3001][3001], C[3001][3001]; struct Z{ int v, t; } mn[3001][3]; deque <Z> dq[3001]; int get_min(int day, int academy) { if (mn[day][0].t != academy && mn[day][0].t != B[academy]) return mn[day][0].v; if (mn[day][1].t != academy && mn[day][1].t != B[academy]) return mn[day][1].v; return mn[day][2].v; } int main() { scanf("%d%d%d%d%d", &N, &M, &S, &E, &T); for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) scanf("%d", A[i]+j); for (int i=1;i<=N;i++) scanf("%d", B+i); for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) C[i][j] = C[i][j-1] + A[i][j]; for (int i=1;i<=M;i++){ for (int j=1;j<=N;j++){ if (i >= S){ int v = get_min(i-S, j) - C[j][i-S]; while (!dq[j].empty() && dq[j].back().v >= v) dq[j].pop_back(); dq[j].push_back({v, i-S}); } while (!dq[j].empty() && dq[j].front().t < i-E) dq[j].pop_front(); if (dq[j].empty() || dq[j].front().v == 1e9) D[i][j] = 1e9; else D[i][j] = dq[j].front().v + T + C[j][i]; } for (int j=0;j<3;j++) mn[i][j] = {(int)1e9, 0}; for (int j=1;j<=N;j++) if (D[i][j] < 1e9){ int v = D[i][j]; if (v < mn[i][0].v) mn[i][2] = mn[i][1], mn[i][1] = mn[i][0], mn[i][0] = {v, j}; else if (v < mn[i][1].v) mn[i][2] = mn[i][1], mn[i][1] = {v, j}; else if (v < mn[i][2].v) mn[i][2] = {v, j}; } } int ans = 1e9; for (int i=1;i<=N;i++){ for (int j=M-E;j<M;j++){ int v = get_min(j, i); if (v == 1e9) continue; ans = min(ans, v + C[i][M]-C[i][j]); } } printf("%d\n", ans); }

4. 조개 줍기 (shell)

NxN 크기의 격자판에 음이 아닌 정수들이 적혀있다. 그리고 다음과 같이 DP 배열을 정의한다.

D[i][j] = 맨 왼쪽 윗 칸인 시작점에서 i행 j열까지 오른쪽과 아래로만 이동하여 갈 때, 지나간 격자칸에 적힌 수 합의 최대값

그리고 N개의 쿼리가 주어지는데, 각 쿼리는 어떤 특정 칸에 적힌 값을 1증가시키거나 1감소시킨다. 이 때, 각 쿼리를 수행한 후 모든 칸의 DP값의 합을 구하는 문제다.

만약 2행2열에 적힌 값이 변할 때, DP 값이 변하는 칸들은 다음과 같이 "계단" 형식으로 나타낼 수 있다.

즉, 각 행에 대해 DP 값이 변하는 영역은 연속한 구간으로 나타낼 수 있다. 이를 이용하여 DP 값이 변하는 "계단" 모양의 영역을 구한 뒤 각 행에 대해 Fenwick tree를 통해 구간에 특정 값을 더하는 연산을 통하여 DP 값을 관리해줄 수 있다.

총 시간복잡도는 $O(N^2 \lg N)$이다.

#include <bits/stdc++.h> using namespace std; typedef long long lld; int N; int A[1501][1501], D[1501][1501]; int bit[1501][1502]; int S[1501], E[1501]; void add(int n, int v, int bit[1502]) { for (;n<=N;n+=n&(-n)) bit[n] += v; } int get(int n, int bit[1502]) { int ret = 0; for (;n;n^=n&(-n)) ret += bit[n]; return ret; } inline int dp(int i, int j){ return D[i][j] + get(j, bit[i]); } int main() { scanf("%d", &N); for (int i=1;i<=N;i++) for (int j=1;j<=N;j++) scanf("%d", A[i]+j); lld ans = 0; for (int i=1;i<=N;i++) for (int j=1;j<=N;j++){ D[i][j] = max(D[i-1][j], D[i][j-1]) + A[i][j]; ans += D[i][j]; } printf("%lld\n", ans); for (int t=1;t<=N;t++){ char c; int y, x; scanf(" %c%d%d", &c, &y, &x); int v = c == 'U' ? 1 : -1; for (int i=y;i<=N;i++) S[i] = N+1, E[i] = 0; S[y] = E[y] = x; for (int ny=y,nx=x;;){ if (nx < N && max(dp(ny-1, nx+1), dp(ny, nx))+v == max(dp(ny-1, nx+1), dp(ny, nx)+v)) nx++; else ny++; if (ny > N) break; E[ny] = nx; } for (int ny=y,nx=x;;){ if (ny < N && max(dp(ny+1, nx-1), dp(ny, nx))+v == max(dp(ny+1, nx-1), dp(ny, nx)+v)) ny++; else nx++; if (nx > N || E[ny] < nx) break; S[ny] = min(S[ny], nx); } for (int i=y;i<=N;i++) if (S[i] <= E[i]){ add(S[i], v, bit[i]); add(E[i]+1, -v, bit[i]); ans += v * (E[i]-S[i]+1); } printf("%lld\n", ans); } }