Problem Solving

📝 문제 정보 # 링크: 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이므로, 그러면 안된다! 따라서 내림차순으로 정렬한뒤 인덱스를 더해서 정리해보자. 예제 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개의 위치 중 하나가 아닙니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31740 🧐 관찰 및 접근 # 문제에서 주어진 그래프는 트리로 보인다. 트리에서는 모든 간선이 단절선이므로 하나만 잘라도 두 컴포넌트로 나뉘는것이 자명하다. 간선을 하나 자르고 나면 서브트리 하나와 나머지 부분으로 나뉜다. 서브트리의 가중치는 트리DP를 활용해 미리 계산해둘 수 있고, 나머지 부분은 전체 가중치 합에서 해당 서브트리의 가중치 합만큼을 빼면 된다. $O(N)$에 계산 가능해보인다. 💻 풀이 # 코드 (C++): int dfs(int c, int p){ par[c] = p; DP[c] = W[c]; for(auto nxt : links[c]){ if(nxt == p) continue; DP[c] += dfs(nxt, c); } return DP[c]; } void solve(){ cin >> N; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } rep(i, 1, N+1) cin >> W[i]; int SUM = dfs(1, -1); int ans = 2e9; pii ans2 = {-1, -1}; rep(i, 2, N+1) if(ans > abs(DP[i] - (SUM - DP[i]))){ ans = abs(DP[i] - (SUM - DP[i])); ans2 = {i, par[i]}; } cout << ans << '\n'; cout << ans2.first << ' ' << ans2.second << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2437 🧐 관찰 및 접근 # $1, 2, 4, 8, 16, \cdots$의 추로 모든 양의 정수를 측정할 수 있음이 자명하다. 이 이유를 살펴보면, $X$라는 무게의 추가 있을때, $X-1$까지의 모든 정수를 표현할 수 없다면 표현할 수 있는 최대치 + 1이 답이 된다. 추를 작은것부터 정렬해서, 빠지는 수 없이 무슨 양의 정수까지 최대한 잴 수 있는지 확인하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<ll> v(N); rep(i, 0, N) cin >> v[i]; sort(all(v)); ll sum = 0; rep(i, 0, N){ if(v[i] > sum + 1){ cout << sum + 1 << "\n"; return; } sum += v[i]; } cout << sum + 1 << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2138 🧐 관찰 및 접근 # 첫번째 / 마지막 전구를 제외하고는, 그리디하게 끄는 규칙이 가능하다. 첫번째 전구를 건드린 경우 / 안건드린 경우 두가지에 대해, 그리디하게 끄고 전체를 끌 수 있는지 확인하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; string S, T; cin >> S >> T; string ret = ""; rep(i, 0, N) ret += (S[i] == T[i] ? "0" : "1"); int ans = 1e9; // don't flip first string tmp = ret; int cnt = 0; rep(i, 1, N){ if(tmp[i-1] == '1'){ cnt++; tmp[i-1] = (tmp[i-1] == '1' ? '0' : '1'); tmp[i] = (tmp[i] == '1' ? '0' : '1'); if(i+1 < N) tmp[i+1] = (tmp[i+1] == '1' ? '0' : '1'); } } if(tmp[N-1] == '0') ans = min(ans, cnt); // flip first tmp = ret; cnt = 1; tmp[0] = (tmp[0] == '1' ? '0' : '1'); tmp[1] = (tmp[1] == '1' ? '0' : '1'); rep(i, 1, N){ if(tmp[i-1] == '1'){ cnt++; tmp[i-1] = (tmp[i-1] == '1' ? '0' : '1'); tmp[i] = (tmp[i] == '1' ? '0' : '1'); if(i+1 < N) tmp[i+1] = (tmp[i+1] == '1' ? '0' : '1'); } } if(tmp[N-1] == '0') ans = min(ans, cnt); if(ans == 1e9) ans = -1; cout << ans << "\n"; } 🔒 구현 코드 잠금