Algorithm

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/24945 🧐 관찰 및 접근 # 서브태스크가 상당히 많고, 문제가 쉽지 않아보인다. 차근차근 해보자. $N = 3$ 브루트포스에 가깝게 풀 수 있을 것 같다. 문자는 어차피 최대 3개 존재하므로, 3개에 대해 $X$가 가질 수 있는 경우의 수 $3^3$가지, $Y$가 가질 수 있는 경우 $3^3$가지를 전이하면서 다익스트라로 풀 수 있을 것 같다. ㅇㅋ 된당 $S_i = a$ 모든 문자가 a라면? $X$에 들어있는 문자 개수, $Y$에 들어있는 문자 개수 두가지를 이용해서 $N^2$ 정점 다익스트라가 가능해보인다. $N \leq 30$ 이제부터 진짜로 어떻게풀어야하는지 고민해봐야할 것 같은데… 일단 복사할 문자 $Y$는 $X$의 substr이어야할 것이다. 그럼 $Y$가 될 수 있는 경우의수는 $O(N^2)$이고 $X$를 만들때든, $Y$를 만들기위해 빌드업하고 있을때든 결국 $X$도 $X$의 substr로 존재해야한다. 이것도 경우의수가 $O(N^2)$ 인 것 같다. $Y$를 붙일 수 있는지 검사하는? 그런것들이 전처리를 안하면 $O(N)$쯤 되어보이니, 아마 종합해서 $O(N^5)$정도로 풀 수 있지 않나? 근데 DP 전이식이 헷갈린다. 이게 상호 참조가 없나? 비용들이 달라서 다익으로 해야될 것 같은데. $\text{DP}[x][y]$: 현재 $X$에 $x$, $Y$에 $y$가 들어있다고 하자. $A$ 연산을 거치면 $x$에 한개가 붙고, $y$는 그대로다. $B$ 연산을 거치면 $x$가 빈 문자열이 되고, $y$는 $x$의 값으로 갱신된다. $C$연산을 거치면 $x = x + y$가 되고, $y$는 그대로다. 아하, 생각보다 $y$가 갱신될일이 없다. 그리고 $y$가 갱신된다면 $x$가 빈 문자열이 된 상태에서 시작한다! 복사하고 붙여넣는 과정을 그냥 해버렸다고 생각하는게 더 쉬울 것 같다. $\text{DP}[i][j]$ : $S_i$~$S_j$까지 만드는 최소비용이라고 하자. 이건 $\text{DP}[i][j-1]$ 후 $A$연산을 하거나 어떤 $i \leq i', j' \leq j$가 있어서 그친구를 복사한 후 붙여넣기를 여러번 하거나. 이건 그리디하게 되는듯? 한번 짜보자. 오!!! 이걸로 대충 $30^5$정도는 성공했다! $N \leq 200$ 이제 $O(N^4)$는 16억이니 빡세고, $O(N^3\log{N})$쯤 까지는 줄여야하는데… 섭태 5는 세제곱, 섭태 6은 제곱로그겠다. 음, 위에서 했던 관찰대로 $Y$에 복사해서 넣으면 $X$는 초기화돼서 시작하므로, DP를 $B$연산으로 $Y$에 복사한거까지 했을 때를 기준으로 하자. 젤 중요한거는 저 그리디하게 비교하면서 뒤로 슝슝슝 가는 파트인 것 같다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> S >> A >> B >> C; if(N >= mxN) { cout << -1 << "\n"; return; } rep(i, 0, N+1) rep(j, 0, N+1) DP[i][j] = LLONG_MAX; rep(i, 0, N+1) rep(j, i+1, N+1) DP[i][j] = A * (j-i) + B; const mint base = 131; const mint2 base2 = 137; vector<mint> hsh(N+1), pw(N+1); vector<mint2> hsh2(N+1), pw2(N+1); hsh[0] = 0; pw[0] = 1; hsh2[0] = 0; pw2[0] = 1; rep(i, 0, N){ hsh[i+1] = hsh[i] * base + S[i]; pw[i+1] = pw[i] * base; hsh2[i+1] = hsh2[i] * base2 + S[i]; pw2[i+1] = pw2[i] * base2; } auto getHash = [&](int l, int r) -> pair<ll, ll>{ ll ret1 = (hsh[r] - hsh[l] * pw[r-l]).get(); ll ret2 = (hsh2[r] - hsh2[l] * pw2[r-l]).get(); return {ret1, ret2}; }; ll ans = N*A; rep(L, 1, N+1){ // A 연산 앞뒤에 붙여서 전이할 때 if(L >= 2) rep(s, 0, N){ if(s+L > N) break; int e = s+L; DP[s][e] = min(DP[s][e], DP[s+1][e]+A); DP[s][e] = min(DP[s][e], DP[s][e-1]+A); } // 해당 문자열을 복사하는 최소 비용 map<pair<ll,ll>, vector<int>> mp; rep(s, 0, N){ if(s+L > N) break; int e = s+L; mp[getHash(s, e)].push_back(s); } // 복사 연산으로 전이 for(auto& [_, v]: mp){ int sz = v.size(); ll mn = 1e18; for(auto s: v) mn = min(mn, DP[s][s+L]); // 다음에 갈 수 있는 위치 vector<int> nxt(sz, sz); for(int i = 0, j = 0; i < sz; i++){ while(j < sz && v[j] < v[i]+L) j++; nxt[i] = j; } rep(i, 0, sz){ int s_pos = v[i]; int cidx = i; int cnt = 0; while(cidx < sz){ cnt++; int e_pos = v[cidx]+L; if(e_pos > N) break; DP[s_pos][e_pos] = min(DP[s_pos][e_pos], mn + (C * cnt) + ((e_pos - s_pos) - (L * cnt)) * A + B); cidx = nxt[cidx]; } } } } ans = min(ans, DP[0][N] - B); cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/27844 번역 문제 번역 # $N$개의 목초지가 있고 ($2 \le N \le 2\cdot 10^5$), $N-1$개의 도로로 연결되어 트리를 형성합니다. 모든 도로를 건너는 데 1초가 걸립니다. 각 목초지는 처음에 풀이 0개이고, $i$번째 목초지의 풀은 초당 $a_i$ ($1\le a_i\le 10^8$) 단위의 속도로 자랍니다. Farmer John은 처음에 목초지 1에 있으며, 모든 목초지의 풀에 비료를 주기 위해 돌아다녀야 합니다. 그가 $x$ 단위의 풀이 있는 목초지를 방문하면, $x$만큼의 비료가 필요합니다. 목초지는 처음 방문할 때만 비료를 주면 되고, 비료를 주는 데는 시간이 걸리지 않습니다.

w## 📝 문제 정보 링크: https://www.acmicpc.net/problem/10044 번역 문제 # JOI 군은 점심으로 중화요리집에서 샤오롱바오를 먹기로 했다. 샤오롱바오는 속재료와 뜨거운 국물을 밀가루 피로 싼 요리로, 먹을 때 국물이 주위로 튀는 것으로 알려져 있다. JOI 군이 주문한 샤오롱바오 세트는 속재료나 국물이 다른 N개의 샤오롱바오로 이루어져 있다. N개의 샤오롱바오는 등간격으로 일렬로 놓여 있으며, 순서대로 1부터 N까지 번호가 매겨져 있다. i번째 샤오롱바오와 j번째 샤오롱바오 사이의 거리는 절댓값 |i - j|이다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28693 🧐 관찰 및 접근 # 문제 상황을 잘 생각해보자. $N$종류의 카드 $2N$개가 있다고 하자. 처음에 고른 두 카드가 같은 쌍이라면, $N-1$ 종류의 카드 $2(N-1)$개가 있는 문제로 바꿀 수 있다. 이 확률은 $\frac{1}{2N-1}$이다. 처음에 고른 두 카드가 다른 쌍이라면, 2번의 기회를 더 써서 (총 3번의 기회로) $N-2$종류의 카드 $2(N-2)$개가 있는 문제로 바꿀 수 있다. 이 확률은 $\frac{2N-2}{2N-1}$이다. …인줄 알았는데 아니다! 생각해보니 $N \geq 3$일때 두개를 깐다고 해서 나머지의 위치를 모른다.. 그렇다면 DP식을 새롭게 세워보자. $DP[N][K]$ : $N$ 쌍의 안깐 카드, $K$종의 위치를 아는 카드가 있을 때의 기댓값 언제나 안깐 카드를 먼저 까는게 최적인데, 그렇다면 $\frac{K}{2N+K}$의 확률로 이미 위치를 아는 카드를 발견하거나 $\frac{2N}{2N+K}$의 확률로 안깐카드를 발견하는데, 이때 $\frac{1}{2N+K-1}$의 확률로 한방에 맞추거나 $\frac{K}{2N+K-1}$의 확률로 원래 알던 쌍이 나와서, 다음 턴에 그걸 맞추거나 $\frac{2N-2}{2N+K-1}$의 확률로 새로운 쌍이 나와서 $K$가 2 늘어나거나 와 같은 식으로 정리된다. 💻 풀이 # 코드 (C++): mint calc(int N, int K){ // $DP[N][K]$ : $N$ 쌍의 안깐 카드, $K$종의 위치를 아는 카드가 있을 때의 기댓값 if(N < 0 || K < 0) return 0; if(N == 0) return mint(K); if(visited[N][K]) return DP[N][K]; visited[N][K] = true; mint res = 0; // 위치를 아는 카드를 뽑는 경우 res += (mint(K) / mint(2*N+K)) * (calc(N, K-1) + 1); // 위치를 모르는 카드를 뽑는 경우 // 두번째 카드가 첫번째 뽑은 카드와 맞는 경우 res += (mint(2*N) / mint(2*N+K)) * (mint(1) / mint(2*N+K-1)) * (calc(N-1, K) + 1); // 두번째 카드가 이미 위치를 아는 카드와 맞는 경우 res += (mint(2*N) / mint(2*N+K)) * (mint(K) / mint(2*N+K-1)) * (calc(N-1, K) + 2); // 두번째 카드가 아예 새로운 카드일 경우 res += (mint(2*N) / mint(2*N+K)) * (mint(2*N-2) / mint(2*N+K-1)) * (calc(N-2, K+2) + 1); return DP[N][K] = res; } void solve(){ int N; cin >> N; cout << calc(N, 0); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/22348 🧐 관찰 및 접근 # 안에서부터 각 동심원에 대해 다음과 같은 DP식을 생각해보자. $\text{DP}[i][j]$: $i$번째 동심원까지 그렸을 때 $j$통의 빨강 페인트를 쓰는 경우의 수 그러면 파란 페인트는 $\sum\limits_{k = 1}^i k - j$ 통 필요하다. 이게 $b$이하면 여유롭게 된다! 시간복잡도는.. $a+b \leq 100000$이므로 500번 안쪽으로 끝날거고, 그에 맞춰 나이브하게 구하면 업데이트에 5만번, 합을 구하는데 5만번이니… 500 * 50000 = 25'000'000번? 근데 테케가 10000개라는 이슈가 있다… 이걸 더 줄여야만 해 아하, 다시 보니까 DP식은 안바뀐다. 그러면 그냥 $500 * 50000$ 테이블을 만들어놓고, 누적합을 이용해서 한번에 구하자. 💻 풀이 # 코드 (C++): void solve(){ vector<vector<mint>> DP(501, vector<mint>(50001, 0)), pfSum(501, vector<mint>(50002, 0)); DP[0][0] = 1; rep(i, 1, 501) rep(j, 0, 50001) DP[i][j] = DP[i-1][j] + (j >= i ? DP[i-1][j-i] : 0); rep(i, 0, 501) rep(j, 0, 50001) pfSum[i][j+1] = pfSum[i][j] + DP[i][j]; int tc; cin >> tc; while(tc--){ ll a, b; cin >> a >> b; ll sum = 0; mint ans = 0; rep(i, 1, 501){ sum += i; if(sum > a + b) break; ans += pfSum[i][min(a, sum) + 1] - pfSum[i][max(0LL, sum - b)]; } cout << ans << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/19545 🧐 관찰 및 접근 # 위쪽동네 소가 $N$마리, 아래쪽 소가 $1$마리라고 해보자. 그러면 연결 방법은 유일하다. 아래 헛간에 모든 위쪽 헛간을 연결해야한다. 아래쪽 소가 $2$마리라고 해보자. 위쪽 동네의 소를 $U_1, U_2, \cdots, U_k$를 헛간 $D_1$에, $U_{k+1}, \cdots U_N$을 $D_2$에 연결해야 한다. 따라서, 다음과 같은 식을 생각해보자. $\text{DP}[i][j]$: 위쪽 동네 소를 $i$마리, 아래쪽 동네 소를 $j$마리를 딱 매칭시켯을때 최솟값 $\text{DP}[i][j] = min_{k < j}(DP[k][j-1] + \text{Cost}[k+1][i][j])$ 위와 같은 느낌의 식이 성립할 것 같은데, Cost를 구하는것도, DP식을 구하는것도 쉽지 않아보인다. 하 이 식이 뭔가 위 / 아래쪽에 대해 대칭인게 의미심장한데… 아 스읍 이게 까다롭네.. 생각해보면, 어떤 간선을 연결했을때, 왼쪽/오른쪽에 남는 개수를 곱한만큼 에 그 경로의 길이를 곱한게 전체에 더해지는데 흠 아니근데 약간 그리디하게 안되나? 위랑 아래랑 같은 좌표인게 있으면 이게 무조건 잇는게 이득이 아니라고? 왜지? 경로가 길어질수가 있나? 그림을 열심히 그리다보니, 결국 간선은 두가지로 나뉜다. Type 1: 반대쪽 정점에 간선이 3개 이상 있고 그 중간에 있어서 해당 간선의 거리에 $N+M-1$이 곱해진다. Type 2: 반대쪽 정점의 가장자리 간선이라서, 해당 간선이 $i - j$를 잇는다면 $(i+j-1)(N+M-(i+j-1))$이 곱해진다. 그러면 각 $\text{DP}[i][j]$에 대해 마지막 친구에 대해 위에 몇개, 아래 몇개 들어있는지를 관리할 수 있지 않을까? 0개일 수는 없고, 1개면 Type1이 되고, 2개 이상이면 원래 간선을 Type2로 처리하고 Type 1을 붙이는 꼴로 될거같은딩 💻 풀이 # 코드 (C++): ll type1(int i, int j){ return dist(i, j) * (N + M - 1); } ll type2(int i, int j){ return dist(i, j) * (i + j + 1) * (N + M - i - j - 1); } void solve(){ cin >> N >> M >> L; rep(i, 0, N) cin >> U[i]; rep(i, 0, M) cin >> D[i]; rep(i, 0, N) rep(j, 0, M) rep(k, 0, 2) rep(l, 0, 2) DP[i][j][k][l] = 1e18; DP[0][0][0][0] = type2(0, 0); rep(i, 0, N) rep(j, 0, M) rep(k, 0, 2) rep(l, 0, 2){ // 아래 헛간에 새로운 위 헛간 붙이기 ll &cur = DP[i][j][k][l]; if(i+1 < N){ ll &ret = DP[i+1][j][0][1]; if(l == 0) ret = min(ret, cur + type2(i+1, j)); else ret = min(ret, cur - type2(i, j) + type1(i, j) + type2(i+1, j)); } // 위 헛간에 새로운 아래 헛간 붙이기 if(j+1 < M){ ll &ret = DP[i][j+1][1][0]; if(k == 0) ret = min(ret, cur + type2(i, j+1)); else ret = min(ret, cur - type2(i, j) + type1(i, j) + type2(i, j+1)); } } ll ans = 1e18; rep(k, 0, 2) rep(l, 0, 2) ans = min(ans, DP[N-1][M-1][k][l]); cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/17790 번역 문제 # 무방향 단순 그래프 G = (V, E)에 대해, V’ ⊆ V인 부분집합 V’를 독립 집합(independent set)이라고 부르는 것은 V’의 어떤 두 원소도 간선으로 연결되어 있지 않을 때입니다. G의 독립 집합을 최대 독립 집합(maximum independent set)이라고 부르는 것은 G에 그보다 엄격하게 더 많은 정점을 가진 독립 집합이 없을 때입니다. 특정한 종류의 연결된 그래프 G가 주어졌을 때, G의 최대 독립 집합의 크기를 구하세요.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/17227 🧐 관찰 및 접근 # 생각하기 쉽게, $N$번 주제인 “그팩주” 근처에서 생각해보자. 어떤 정점에서, 다음 정점 중 $N$번 정점이 있다면 준표는 화제를 그 정점으로 보내면 안된다. 만영이의 차례에서 만영이는 다음 간선중 최대한 기댓값이 높은 정점으로 가려고 한다. 그것들을 하나하나 반려해가는 맛인데.. DP식을 이런식으로 세울 수 있을까? $\text{DP}[i][a]$ : $i$번 정점에서 $a$번사람의 턴일때 기댓값 $\text{DP}[i][jun] = \min\limits_{nxt: links[i]}(\text{DP}[nxt][man])$ $\text{DP}[i][man] = \min\limits_{nxt: links[i]}(\text{DP}[nxt][jun] + cnt)$ 예를들어 만영이가 고르 수 있는 다음 정점이 $N, i, j, k$라고 하고, 기댓값은 각각 $1e9, 10, 10, 9$라고 하자. $N$은 고르면 안되므로, 무조건 반려한다. 그러면 만영이는 10을 고르고, 이때 기댓값은 11이다. 마지막 9를 고르기 위해 3번 반려해버리면 오히려 기댓값이 12이므로, 그러면 안된다! 따라서 내림차순으로 정렬한뒤 인덱스를 더해서 정리해보자. ![[Drawing 2026-02-12 10.30.22.excalidraw.png]] 예제 3번의 그림 💻 풀이 # 코드 (C++): int calc(int cur, int turn){ if(DP[cur][turn] != -1) return DP[cur][turn]; int &ret = DP[cur][turn]; ret = 1e9; if(turn == 0){ // 준표의 턴 for(auto nxt: links[cur]) ret = min(ret, calc(nxt, 1)); return ret; } else{ // 만영이의 턴 vector<int> v; for(auto nxt: links[cur]) v.push_back(calc(nxt, 0)); sort(all(v), greater<int>()); rep(i, 0, v.size()) ret = min(ret, v[i] + i); return ret; } } void solve(){ cin >> N >> E; rep(i, 0, E){ int u, v; cin >> u >> v; links[u].push_back(v); inDeg[v]++; } rep(i, 0, N+1) DP[i][0] = DP[i][1] = -1; DP[N][0] = 1e9; DP[N][1] = 0; int ans = 1e9; rep(i, 1, N+1) if(inDeg[i] == 0) ans = min(ans, calc(i, 1)); if(ans == 1e9) cout << -1 << '\n'; else cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/12008 🧐 관찰 및 접근 # 흠, 결국 마지막에 사용한 모든 숫자들은 하나의 범위로 나타날 것 같다. 범위를 쪼개는 맛의 DP를 할 수 있나? $\text{DP}[i][j]$: $i$~$j$까지의 숫자를 모두 사용해서 만들어진 수 라고 하면 $O(N^2)$의 시간이 걸린다… 이런 느낌으로 $\log$로 바운드 시킬 수 있q을까? $(1, 1, 1, 2)$ 에서 1들을 2로 묶을 수 있는 경우를 각 인덱스에 대해서 표시 $(2, 1, 2), (1, 2, 2)$ 등으로 나타내져을때, 2들을 4로 묶을 수 있는 경우에 대해 표시.. 그러니까, $(1, 1, 1, 2)$는 2로 묶었을때 다음 인덱스는 $(1, 2, -1, 3)$ 처럼 (0-based) 그러면 뒤로 계속 폴짝폴짝 뛰어다니면서 계산하면, 만들 수 있는 최대값인 58에 대해 $O(N)$번 하면 될거같기도..? 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; vector<vector<int>> v(60, vector<int>(N+1, -1)); rep(i, 0, N) v[A[i]][i] = i; int ans = 0; rep(b, 0, 60){ rep(i, 0, N) if(v[b][i] != -1 && v[b][v[b][i]+1] != -1) v[b+1][i] = v[b][v[b][i]+1]; rep(i, 0, N) if(v[b][i] != -1) ans = max(ans, b); } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10108 번역 문제 # 당신은 간식을 좋아하는 애완용 여우를 키우고 있습니다. 서로 다른 위치(데카르트 평면 위의 점으로 표현됨)에 N명의 이웃이 있으며, 각 이웃은 당신의 애완 여우에게 간식을 나눠줍니다. 각 이웃은 무제한으로 간식을 줄 수 있습니다. 원점(여우가 시작하는 위치)은 이 N개의 위치 중 하나가 아닙니다.