Nexon Youth Programming Challenge(NYPC) 2022 본선 풀이

1214 A. 조약돌 순서

처음에 $[1, 2, 3, ..., K]$이 적혀있는 크기 $K$인 배열 $A$가 있다. $i = 1$부터 시작하여 $A_i$와 $A_{i+1}$의 값을 바꾼다. 그리고 $i$를 $1$ 증가시킨다. 만약 $i = K-1$이라면 다음 $i$의 값은 $K$가 아니라, $1$이 된다. 바꾸는 작업을 $N$ 번 하였을 때, 최종 배열의 상태를 구하는 문제다.

 

값을 바꾸는 횟수 $N$이 최대 $10^{18}$로 굉장히 크다. 바꾸는 작업을 $K \times (K-1)$ 번 하면 배열이 원래 상태로 돌아오고, 바꾸는 작업을 $K-1$ 번하면 맨 왼쪽에 있던 값이 맨 오른쪽으로 가는 것을 알 수 있다. 이 점을 이용하여, $O(K)$ 시간복잡도에 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; using lld = long long; int main(){ cin.tie(0)->sync_with_stdio(0); int K; lld N; cin >> K >> N; N %= (lld)K*(K-1); int A[K+1]; for (int i=1;i<=K;i++) A[i] = i; int S = N/(K-1); N %= K-1; rotate(A+1, A+1+S, A+K+1); int i = 1; while (N--){ swap(A[i], A[i+1]); i = i+1 < K ? i+1 : 1; } for (int i=1;i<=K;i++) cout << A[i] << ' '; cout << '\n'; }

1214 B. 짝 맞는 문자열

A, B, C로 이루어진 길이 $N$인 문자열이 주어진다. 이 문자열에서 최소 개수의 문자를 제거하여 같은 문자가 두 개씩 반복되게 하는 문제다. 즉, 제거할 문자를 모두 제거한 후, $1$ 이상인 $i$에 대해 $2i-1$ 번째 문자와 $2i$ 번째 문자가 같아야 하며, 이 둘이 같으면 짝이 맞는다고 하자.

 

D[i][j] = 문자열의 길이 $i$인 접두사에서 상태가 $j$일 때 제거하고 남은 문자의 최대 개수라고 정의하자.

상태 $j$는 만약 모든 문자가 짝이 맞는다면 $j = 0$, 맨 마지막 문자를 제외한 모든 문자가 짝이 맞는다면 $j$는 맨 마지막 문자로 정의한다.

 

문제에서 요구하는 답은 D[N][0]이 되며, 이 DP 배열은 시간복잡도 $O(N)$만에 구할 수 있다.

#include <bits/stdc++.h> using namespace std; int main(){ cin.tie(0)->sync_with_stdio(0); string S; cin >> S; int N = size(S); int D[N+1][4]; for (int i=0;i<=N;i++) for (int j=0;j<4;j++) D[i][j] = -1; auto put_max = [](auto& a, auto b){ a = max(a, b); }; D[0][0] = 0; for (int i=0;i<N;i++){ for (int j=0;j<4;j++) put_max(D[i+1][j], D[i][j]); if (D[i][0] >= 0) put_max(D[i+1][S[i]-'A'+1], D[i][0]+1); if (D[i][S[i]-'A'+1] >= 0) put_max(D[i+1][0], D[i][S[i]-'A'+1]+1); } cout << D[N][0] << '\n'; }

1214 C / 1519 A. 빙고

$N \times M$ 크기의 빙고판이 있다. 칸에 적힌 수는 알 수 없고, 사회자가 부르는 수도 알 수 없다. $i$ 번째 행을 완성하면 $A_i$점을 획득하며, $j$ 번째 열을 완성하면 $B_j$점을 획득한다. 사회자가 번호를 $K$ 개 부를 때, 얻을 수 있는 최대 점수를 구하는 문제다.

 

$r$ 개의 행을 먼저 완성한다고 하자. 그러면 불러야 하는 수의 개수는 $r \times M$개다. 그 뒤로 열만 완성한다고 했을 때, 완성시킬 수 있는 열의 최대 개수는 $\lfloor\frac{K - r \times M}{N-1}\rfloor$로 정해진다. 획득할 수 있는 점수가 높은 행들과 열들을 우선적으로 완성하는 것이 제일 좋다. $0$ 이상 $N$ 미만인 모든 $r$에 대해 완성시킬 수 있는 열의 개수를 구하고, 점수를 계산하여, 그중 가장 높은 점수를 구하여 문제를 해결할 수 있다. 단, $K = N \times M$인 경우에 대한 예외 처리가 필요하다. 시간복잡도는 $O(N+M)$이다.

#include <bits/stdc++.h> using namespace std; using lld = long long; int main(){ cin.tie(0)->sync_with_stdio(0); int N, M; lld K; cin >> N >> M >> K; int A[N+1], B[M+1]; for (int i=1;i<=N;i++) cin >> A[i]; for (int i=1;i<=M;i++) cin >> B[i]; sort(A+1, A+N+1, greater<int>()); sort(B+1, B+M+1, greater<int>()); lld P[N+1]{}, Q[M+1]{}; for (int i=1;i<=N;i++) P[i] = P[i-1]+A[i]; for (int i=1;i<=M;i++) Q[i] = Q[i-1]+B[i]; if (K == (lld)N*M){ lld ans = 0; for (int i=1;i<=N;i++) ans += A[i]; for (int i=1;i<=M;i++) ans += B[i]; cout << ans << '\n'; return 0; } lld ans = 0; for (int rows=0;rows<N;rows++){ if ((lld)M*rows > K) break; int cols = (K-(lld)M*rows) / (N-rows); ans = max(ans, P[rows]+Q[cols]); } cout << ans << '\n'; }

1214 D / 1519 B. 야찌

$1$ 이상 $6$ 이하의 수가 적힌 $N$ 개의 카드가 있는 카드 더미가 있다. 그리고 5장의 종이가 있다. 각 턴마다 카드 더미 위에서 카드 5장을 뽑아 순서대로 종이에 적는다. 그리고 최대 한 번 수를 지울 종이를 고르고, 카드 더미에서 카드를 다시 뽑아 지운 종이 위에 수를 적을 수 있다. 만약, 종이 5장에 적힌 수가 모두 같다면 야찌다. 카드 더미에 대한 정보가 주어졌을 때, 가능한 야찌의 최대 횟수를 구하는 문제다.

 

D[i] = 카드 더미에서 총 $i$ 장의 카드를 뽑았을 때, 할 수 있는 야찌의 최대 횟수라고 정의하자.

 

문제에서 요구하는 답은 $\max(D_i)$이다. 한 턴에 뽑을 수 있는 카드의 최대 개수는 10장이므로, $O(N)$ 시간에 DP를 구현할 수 있다. 다만, $N$의 최대값이 $10^6$이므로, 구현에 따라 시간초과가 날 수도 있다. 아래 첨부된 코드는 비트마스크를 이용한 전처리 작업으로 최대한 상수를 줄였다.

#include <bits/stdc++.h> using namespace std; int main(){ cin.tie(0)->sync_with_stdio(0); int N; string S; cin >> N >> S; int A[N+1]; for (int i=1;i<=N;i++) A[i] = S[i-1]-'0'; bool can[11][1024]{}; vector<int> info[11][1024]; for (int i=5;i<=10;i++){ for (int msk=0;msk<1<<i;msk++){ auto& _info = info[i][msk]; int arr[i]; for (int j=0;j<i;j++) arr[j] = msk>>j&1; int cnt = 0; for (int j=0;j<5;j++) if (arr[j]) cnt++; int discard = i-5; for (int j=0;j<5;j++) if (!arr[j] && size(_info) < discard) _info.push_back(j+1); for (int j=0;j<5;j++) if (arr[j] && size(_info) < discard) _info.push_back(j+1); cnt = min(cnt, 5-discard); for (int j=5;j<i;j++) if (arr[j]) cnt++; if (cnt == 5) can[i][msk] = 1; } } vector<int> D(N+1, -1); pair<int, int> from[N+1]; D[0] = 0; for (int i=0;i<N;i++) if (D[i] >= 0){ for (int num=1;num<7;num++){ int msk = 0; for (int j=1;j<=10;j++){ if (i+j > N) break; if (A[i+j] == num) msk ^= 1<<j-1; if (j >= 5){ if (D[i+j] < D[i]+can[j][msk]){ D[i+j] = D[i]+can[j][msk]; from[i+j] = make_pair(j, msk); } } } } } int ans = -1, t; for (int i=1;i<=N;i++) if (ans < D[i]){ ans = D[i]; t = i; } vector<vector<int>> path; while (t > 0){ auto [len, msk] = from[t]; path.push_back(info[len][msk]); t -= len; } reverse(begin(path), end(path)); cout << ans << '\n' << size(path) << '\n'; int turn = 0; for (auto& arr: path){ cout << "Turn " << ++turn << '\n'; if (arr.empty()) cout << "0\n"; else{ cout << "1\n" << size(arr); for (int v: arr) cout << ' ' << v; cout << '\n'; } } }

1214 E. 삼각

정점 $N$ 개와 양방향 간선 $M$ 개로 이루어진 그래프가 주어진다. 각 간선에는 길이가 있다. 정점 $S$가 주어진다. 정점 $S$에서 시작하여 어떤 정점 $A$로 이동했다가, 다른 정점 $B$로 이동하고, 다시 정점 $S$로 돌아오는 경로 중에 정점 $S$를 중간에 방문하지 않으면서 가장 길이가 짧은 경로를 구하는 문제다.

 

이 문제 풀이의 핵심 아이디어는 서로 인접한 정점 두 개를 정점 $A$와 정점 $B$만 답의 후보로 두어도 문제에서 요구하는 답을 올바르게 구한다는 점이다. 즉, 입력으로 주어진 정점 $S$에서 각 정점으로 가는 최단 거리를 구한 뒤, 정점 $a$와 정점 $b$를 연결하는 길이 $c$인 간선이 있다면, 정점 $S$에서 정점 $a$로 오는 최단 거리 값 + 정점 $S$에서 정점 $b$로 오는 최단 거리 값 + $c$를 구하고, 그중 가장 작은 값을 구하면 정답을 구할 수 있다. 시간복잡도는 $O(N + M \lg N)$이다.

 

문제 풀이와 크게 상관 없는 관찰 중, 답이 되는 싸이클에 포함된 간선의 개수는 최대 $4$ 개라는 것도 증명할 수 있다. 이 점을 이용하여, 서브태스크를 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; using lld = long long; constexpr lld inf = 4e18; int main(){ cin.tie(0)->sync_with_stdio(0); int N, M, S; cin >> N >> M >> S; vector<vector<pair<int, int>>> con(N+1); for (int i=1;i<=M;i++){ int a, b, c; cin >> a >> b >> c; con[a].emplace_back(b, c); con[b].emplace_back(a, c); } vector<lld> dist(N+1, inf); priority_queue<pair<lld, int>> pq; dist[S] = 0; pq.emplace(0, S); while (!pq.empty()){ auto [d, n] = pq.top(); pq.pop(); if (dist[n] != -d) continue; for (auto [t, v]: con[n]){ if (dist[t] > dist[n]+v) dist[t] = dist[n]+v, pq.emplace(-dist[t], t); } } lld ans = inf; for (int i=1;i<=N;i++){ for (auto [j, d]: con[i]){ if (i == S || j == S) continue; ans = min(ans, dist[i]+dist[j]+d); } } cout << ans << '\n'; }

1519 C. 덧셈 프로그램

크기 $N$인 정수 배열 $A$가 있고, $M$ 개의 명령어로 구성된 프로그램이 있다. 명령어는 $A_i$에 $A_j$를 더하는 꼴을 한다. 이 프로그램을 총 $L$ 번 실행하는데, 각 실행마다 배열의 초기값이 다를 수 있다. 각 실행마다 프로그램이 종료되는 시점에서 $A_1$의 값을 구하는 문제다.

 

크기 $N$인 정수 배열 $B$를 생각하자. $B$의 초기값은 $B_1 = 1$이고, 나머지는 $0$이다. 배열 $B$에서 입력으로 주어진 프로그램의 명령어를 반대로 실행한다. 명령어의 순서도 반대가 되어야 하고, $A_i$에 $A_j$를 더하는 명령어가 있다면, $B_j$에 $B_i$를 더하자. 실행 이후의 $B_i$ 값은 주어진 프로그램에서 $A_i$의 초기값이 최종적으로 $A_1$에 몇번 더해졌는지를 나타낸다.

 

이를 이용하여 각 프로그램 실행마다, 프로그램이 종료되는 시점에서 $A_1$의 값을 빠르게 구할 수 있다. 초기값이 $0$이 아닌 $A_i$의 총개수를 $K$라고 했을 때, 시간복잡도는 $O(M+L+K)$이다.

#include <bits/stdc++.h> using namespace std; using lld = long long; constexpr int MOD = 1e9 + 7; int main(){ cin.tie(0)->sync_with_stdio(0); int N, M, L; cin >> N >> M >> L; int X[M+1], Y[M+1]; for (int i=1;i<=M;i++) cin >> X[i] >> Y[i]; int A[N+1]{}; A[1] = 1; for (int i=M;i;i--){ A[Y[i]] += A[X[i]]; if (A[Y[i]] >= MOD) A[Y[i]] -= MOD; } for (int i=1;i<=L;i++){ int n; cin >> n; int ans = 0; for (int j=0;j<n;j++){ int a, b; cin >> a >> b; ans = (ans+(lld)A[a]*b)%MOD; } cout << ans << '\n'; } }

1519 D. 적절한 점

$x$ 좌표가 $1$ 이상 $W$ 이하이며, $y$ 좌표가 $1$ 이상 $H$ 이하인 2차원 정수 좌표 공간이 있다. 여기에 $K$ 개의 점 집합이 있다. 그리고 각 집합에 대해 $C_i$ 값이 입력으로 주어진다. 적절한 점이란, 모든 $i$에 대해 점 집합 $i$에서 그 점보다 $x$ 좌표가 같거나 작고, 그 점보다 $y$ 좌표가 같거나 작은 점의 개수가 정확히 $C_i$가 되는 점을 말한다. 이때, 적절한 점의 개수를 구하는 문제다.

 

풀이의 아이디어는 간단하다. 어떤 $x$ 좌표에 대해 적절한 점은 연속된 구간으로 표현된다. 각 점 집합에 대해 독립적으로 적절한 점의 $y$ 좌표 구간을 구하고, 교집합을 구하면 된다.

 

좌표 압축과 자료 구조를 이용하여 빠른 시간복잡도로 구현할 수 있다. 전체 점의 개수를 $N$이라고 했을 때, 풀이의 시간복잡도는 $O(N \lg N)$이다.

#include <bits/stdc++.h> using namespace std; using lld = long long; int W, H, K; int main(){ cin.tie(0)->sync_with_stdio(0); cin >> W >> H >> K; vector<tuple<int, int, int>> A; A.emplace_back(1, 0, 0); A.emplace_back(W+1, 0, 0); for (int i=1;i<=K;i++){ int n; cin >> n; for (int j=0;j<n;j++){ int x, y; cin >> x >> y; A.emplace_back(x, y, i); } } sort(begin(A), end(A)); struct PointSet{ map<int, int> val = {{1, 0}}; int bound, cnt = 0, pivot = 0, nxt; void add(int y){ val[y]++; if (!pivot) pivot = y, nxt = H+1; if (y <= pivot) cnt++; auto it = val.find(pivot); while (cnt > bound && it != val.begin()){ cnt -= it->second; it--; } while (cnt < bound){ auto nxt = it; nxt++; if (nxt == val.end() || cnt+nxt->second > bound) break; cnt += nxt->second; it = nxt; } pivot = it->first; it++; nxt = it == val.end() ? H+1 : it->first; } }; PointSet ps[K+1]; for (int i=1;i<=K;i++){ int v; cin >> v; ps[i].bound = v; } priority_queue<pair<int, int>> P, Q; int S[K+1], E[K+1]; for (int i=1;i<=K;i++){ if (!ps[i].bound) S[i] = 1, E[i] = H+1; else S[i] = 1, E[i] = 0; P.emplace(S[i], i); Q.emplace(-E[i], i); } auto update = [&](int i, int s, int e){ if (S[i] == s && E[i] == e) return; S[i] = s; E[i] = e; P.emplace(S[i], i); Q.emplace(-E[i], i); }; lld ans = 0; int prv = 0; for (auto [x, y, i]: A){ if (prv && prv != x){ while (S[P.top().second] != P.top().first) P.pop(); while (E[Q.top().second] != -Q.top().first) Q.pop(); int s = P.top().first; int e = -Q.top().first; if (s < e) ans += (lld)(e-s)*(x-prv); } prv = x; if (!i) continue; ps[i].add(y); if (ps[i].cnt == ps[i].bound) update(i, ps[i].pivot, ps[i].nxt); else update(i, 1, 0); } cout << ans << '\n'; }

1519 E. 지름길

정점 $N$ 개와 양방향 간선 $M$ 개로 이루어진 그래프가 주어진다. 각 간선에는 길이가 있다. 정점 $S$와 정점 $T$가 주어진다. 정점 $S$에서 정점 $i$로 가는 최단 거리와 정점 $i$에서 정점 $T$로 가는 최단 거리가 유지되도록 최소 개수의 간선만 남기는 문제다.

 

이 문제 풀이에 대한 접근은 최단 거리 트리(Shortest-path tree)를 생각해보면 된다. 정점 $S$에 대한 최단 거리 트리와 정점 $T$에 대한 최단 거리 트리가 원래 그래프와 동일하도록 최소 개수의 간선만 남기면 된다. 이 점을 생각해보면, 문제에서 요구하는 답은 최대 $2(N-1)$이라는 것을 알 수 있다.

 

최소 개수의 간선을 남겨야하므로, 최대한 많은 간선이 정점 $S$에 대한 최단 거리 트리와 정점 $T$에 대한 최단 거리 트리에 동시에 존재하는 것이 유리하다. 두 최단 거리 트리에 모두 존재할 수 있는 간선 후보들을 구한 뒤, 그 후보 중에서 동시에 존재할 수 있는 간선의 최대 개수를 구하면 된다. 동시에 존재할 수 있는 간선의 최대 개수는 이분 그래프에서 최대 매칭을 통해 구할 수 있다. 최대 매칭의 개수가 $F$라고 하면, 답은 $2(N-1) - F$가 된다. 이분 매칭은 Hopcroft-Karp 알고리즘을 구하는 것이 가장 빠르며 이 문제를 해결하는 전체 시간복잡도는 $O(N + M \sqrt{N})$이다.

 

풀이의 원리를 이해했다면, 남겨야하는 간선을 구하는 것은 간단하다. 첨부된 코드를 참고하자.

#include <bits/stdc++.h> using namespace std; using lld = long long; constexpr lld inf = 1e18; int main(){ cin.tie(0)->sync_with_stdio(0); int N, M, S, T; cin >> N >> M >> S >> T; vector<pair<int, int>> con[N+1]; tuple<int, int, int> edges[M+1]; for (int i=1;i<=M;i++){ int a, b, c; cin >> a >> b >> c; con[a].emplace_back(b, c); con[b].emplace_back(a, c); edges[i] = {a, b, c}; } lld D[2][N+1]; auto dijkstra = [&](int st, lld dist[]){ fill(dist+1, dist+N+1, inf); priority_queue<pair<lld, int>> que; dist[st] = 0; que.emplace(0, st); while (!que.empty()){ auto [d, n] = que.top(); que.pop(); if (dist[n] != -d) continue; for (auto [t, v]: con[n]){ if (dist[t] > dist[n]+v){ dist[t] = dist[n]+v; que.emplace(-dist[t], t); } } } }; dijkstra(S, D[0]); dijkstra(T, D[1]); int selectedA[N+1]{}, selectedB[N+1]{}; vector<pair<int, int>> bcon[N+1]; for (int i=1;i<=M;i++){ auto [a, b, c] = edges[i]; int p = 0, q = 0; if (D[0][a]-D[0][b] == c) p = a; if (D[0][b]-D[0][a] == c) p = b; if (D[1][a]-D[1][b] == c) q = a; if (D[1][b]-D[1][a] == c) q = b; if (p && q) bcon[p].emplace_back(q, i); if (p) selectedA[p] = i; if (q) selectedB[q] = i; } bool used[N+1]{}; int match[N+1]{}, matchE[N+1]{}, dist[N+1]; auto bfs = [&](){ fill(dist+1, dist+N+1, 1e9); queue<int> que; for (int i=1;i<=N;i++) if (!used[i]) que.push(i); while (!que.empty()){ int q = que.front(); que.pop(); for (auto [t, _]: bcon[q]){ if (int m = match[t]; m && dist[m] == 1e9) dist[m] = dist[q]+1, que.push(m); } } }; function<bool(int)> dfs = [&](int n){ for (auto [t, e]: bcon[n]){ if (int m = match[t]; !m || dist[m] == dist[n]+1 && dfs(m)){ used[n] = 1; match[t] = n; matchE[t] = e; return 1; } } dist[n] = 1e9; return 0; }; int matched = 0; for (;;){ bfs(); int flow = 0; for (int i=1;i<=N;i++) if (!used[i] && dfs(i)) flow++; if (!flow) break; matched += flow; } int K = 2*(N-1)-matched; cout << K << '\n'; for (int i=1;i<=N;i++) if (match[i]) selectedA[match[i]] = selectedB[i] = matchE[i]; bool edge_used[M+1]{}; for (int i=1;i<=N;i++) edge_used[selectedA[i]] = edge_used[selectedB[i]] = 1; for (int i=1;i<=M;i++) if (edge_used[i]) cout << i << ' '; cout << '\n'; }