DP

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14587 🧐 관찰 및 접근 # 전처리를 적당히 할 수 있을까? 이분탐색을 좀 하면서 밀면서 하면, 특정 도미노를 한쪽으로 밀었을때 어디까지 넘어가는지 할 수 있나? 아, min/max 세그먼트 트리로 되는거같다 마지막은 그리디가 아니라 DP로 해야한다! 아니근데 X가 정렬되어 주어지지 않는다;;;;; 그래도 구현이 막 어렵지 않은듯 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<ll> X(N), H(N); vector<pll> dominos(N); rep(i, 0, N) cin >> dominos[i].first >> dominos[i].second; sort(all(dominos)); rep(i, 0, N){ X[i] = dominos[i].first; H[i] = dominos[i].second; } SegmentTreeMinMax ST_min(N), ST_max(N); // calc leftmost ST_min.set(0, 0); rep(i, 1, N){ ll val = X[i] - H[i]; auto idx = lower_bound(all(X), val) - X.begin(); auto Q = ST_min.query(idx, i-1); ST_min.set(i, min((ll)i, ST_min.query(idx, i-1).first)); } // calc rightmost ST_max.set(N-1, N-1); rrep(i, 0, N-1){ ll val = X[i] + H[i]; auto idx = upper_bound(all(X), val) - X.begin() - 1; auto Q = ST_min.query(i+1, idx); ST_max.set(i, max((ll)i, ST_max.query(i+1, idx).second)); } vector<int> DP(N, 1e9); DP[0] = 1; DP[ST_max.get_val(0)] = 1; rep(i, 1, N){ int lft = ST_min.get_val(i)-1; if(lft < 0) DP[i] = 1; else DP[i] = min(DP[i], DP[lft] + 1); int rht = ST_max.get_val(i); DP[rht] = min(DP[rht], DP[i-1] + 1); } cout << DP[N-1]; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1006 🧐 관찰 및 접근 # 유명한 통곡의 벽 문제 초라기 문제가 $2 \times N$의 원형이라 조금 곤란하다. 쉬운 경우부터 생각하자. $1 \times N$의 선형이라면, 계단 수처럼 DP로 풀 수 있을 것 같다. $2 \times N$의 선형이라도 DP로 가능한 것 같다. 두칸 전에서 오는 것에 대해 가로두개 / 위에 가로와 아래 따로 / 아래 가로와 위에 따로 한칸 전에서 오는 것에 대해 세로 / 위아래 따로 이 5가지 경우에서 가능한 것 같다! 그런데 원형이라 조금 곤란한데.. 뭔가 케이스를 나눌 수 있을 것 같긴 하다. 선형으로 생각했을때 맨 왼쪽에 대해, 그게 반대쪽과 이어진경우 / 안이어진경우. 위아래니까 각각 두가지, 총 4가지 경우의수를 따지면 될듯? 근데 이걸 어떻게 깔끔하게 코딩하지? 큰일났다. 둘다 반대쪽과 이어진 경우는 문제를 한칸 밀어서 풀기만 하면 되는 것 같은데, 한쪽만 밀린 경우가 까다롭다. 그런데 사실 모든 칸이 지그재그로 연결된 경우 빼고는 언젠가는 선형으로 풀어도 되는 타이밍이 있는 것 같다! 위에서 말한 타이밍은 예제에서는 $1-2, 10-11, 3-4, \cdots$로 연결된 느낌과 같다. 시간복잡도가 $O(NW)$이 되긴 하는데, 돌만하지 않을까? 저 지그재그만 예외처리를 해버리자. ㄲㅂ 시간초과네. 테케가 여러개라 그런 것 같다. 엥? 이거 그냥 길이를 $2N$으로 늘려서 하면 되지 않을까? …인줄알았는데 전이식 자체부터 두개 전에서 땡겨오다보니 차분트릭이 안먹히는것 같다. 전이식 자체에서도 여러칸 단위로 지그재그로 오면 할 수 있는게 없다.. DP에서, 상태공간을 조금 더 정의해보자. $\text{DP}[i][j]$라고 하면, i번째칸까지 봤을때 위아래 찬게 j상황이라고 생각해보자. $j = 0, 1, 2, 3$에서 위아래 모두 빔, 위 참, 아래 참, 위아래 모두 참과 같은 느낌이다. 이렇게해서 전이식을 잘 세우면 저 예외상황들을 처리하기 용이할 것 같다. 3번은 0번과 같으니 없애고, 나머지 3개로 정말 잘 처리해보자… 💻 풀이 # 코드 (C++): void solve(){ ll N, W; cin >> N >> W; vector<array<ll, 2>> v(N); rep(i, 0, N) cin >> v[i][0]; rep(i, 0, N) cin >> v[i][1]; auto calc = [&](bool con1, bool con2) { vector<array<ll, 3>> DP(N+1); // 0: 둘다끝, 1: 위가 튀어나감, 2: 아래가 튀어나감 rep(i, 0, N+1) rep(j, 0, 3) DP[i][j] = 1e18; DP[0][0] = 0; if(con1) DP[0][1] = 0; if(con2) DP[0][2] = 0; if(con1 && con2) DP[1][0] = 0; rep(i, 1, N+1){ DP[i][0] = min(DP[i][0], DP[i-1][0] + (v[i-1][0] + v[i-1][1] <= W ? 1 : 2)); DP[i][0] = min(DP[i][0], DP[i-1][1] + 1); DP[i][0] = min(DP[i][0], DP[i-1][2] + 1); if(i-2 >= 0 && v[i-2][0]+v[i-1][0] <= W && v[i-2][1]+v[i-1][1] <= W){ DP[i][0] = min(DP[i][0], DP[i-2][0] + 2); } DP[i][1] = min(DP[i][1], DP[i][0] + 1); if((i == N && con1) || (i < N && v[i-1][0] + v[i][0] <= W)){ DP[i][1] = min(DP[i][1], DP[i-1][0] + 2); DP[i][1] = min(DP[i][1], DP[i-1][2] + 1); } DP[i][2] = min(DP[i][2], DP[i][0] + 1); if((i == N && con2) || (i < N && v[i-1][1] + v[i][1] <= W)){ DP[i][2] = min(DP[i][2], DP[i-1][0] + 2); DP[i][2] = min(DP[i][2], DP[i-1][1] + 1); } } if(!con1 && !con2) return DP[N][0]; if(con1 && !con2) return DP[N-1][2] + 1; if(!con1 && con2) return DP[N-1][1] + 1; if(con1 && con2) return DP[N-1][0] + 2; }; auto origin = v; ll ans = 2*N; rep(con1, 0, 2) rep(con2, 0, 2){ if(con1 && v[0][0] + v[N-1][0] > W) continue; if(con2 && v[0][1] + v[N-1][1] > W) continue; ans = min(ans, calc(con1, con2)); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2803 🧐 관찰 및 접근 # 비트마스킹적으로 접근해보면, 여러 장난감 상자들의 or 연산결과가 $1111111..$이 되도록 하는 조합의 개수를 찾으면 되는 것 같다. $N$에 대해 생각하긴 까다로우므로, $M \leq 20$인 것을 이용해서 $M$에 대한 비트마스킹된 상자의 수로 생각해보자. 이후 과정을 포함배제로 진행하면 $O(2^N \times 2^N)$이겠지만, 우리는 SOS DP를 이용해서 $O(N2^N)$ 에 계산할 수 있음을 알 수 있다. 그런데 그냥 기본적인 SOS DP랑은 세팅이 조금 다른가? 고민해보자. 기본적인 SOS DP는 해당 비트마스크의 부분집합의 원소 개수의 합이다. 이번에 구해야하는건 해당 비트마스크를 만들어줄 수 있는 조합의 개수인데.. 결국 어떤 상자 $110011$을 골랐다고 생각해보자. 그러면, $??11??$ 인걸 모두 고르면 된다. 이걸 부분집합으로 세긴 힘들지만, 뒤집어서 생각한다면 $??00??$을 찾는 것이고, 이건 $110011$의 부분집합의 개수와 같은 것 같다! 자기 자신을 세지 않도록 조심하자. 그런데 저 방법으로 세면, 두개의 or연산밖에 고려하지 못한다… 3개 이상인걸 고려하려면 DP 설계를 조금 더 잘해야 할 것 같다. 아하, 원래게 $??11??$인 개수를 안다면, 여기에서 한개 이상만 고르면 된다. 그 개수를 $\text{cnt}$라고 하면, $2^{\text{cnt}} - 1$이 성립하는거 같기도? 근데 다시 생각해보니, 뭐랄까 원래가 $??10??$$ 인거랑 $??01??$$ 인거랑이 합쳐져서 되는것들을 못세는거..같기도? 연산해서 $11$을 만들기 위해선, $(11 + 10 + 01 + 00)^2$ 같은 느낌으로 생각해보자. 저 연산 결과는 $$ 11^2 + 10^2 + 01^2 + 00^2 + \\ 2(11\cdot10 + 11\cdot01 + 11\cdot00 + 10\cdot01 + 10\cdot00 + 01\cdot00) $$ 이고, 잘 고민해보니 $11$의 부분집합의 제곱 - $11, 01$의 부분집합의 제곱 - $00$의 부분집합의 제곱을 하면 깔끔하게 $11^2 + 2(11\times10 + 11\times01 + 11\times00 + 10\times01)$이 된다. 아니 잠깐만, 저 느낌을 그대로 가져가면 그냥 부분집합의 합으로 SOS DP를 한다음에 포함배제를 때려버리면 어떻게든 된다. 연산결과가 $11...11$인놈들 - $(01...11), (10..111)...$ + $...$ 이렇게 하면 되는구나! 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<int> A(N); rep(i, 0, N){ int K; cin >> K; int ret = 0; rep(j, 0, K){ int x; cin >> x; ret |= (1 << (x-1)); } A[i] = ret; } vector<int> SOS(1 << M, 0); for(auto x: A) SOS[x] += 1; rep(i, 0, M) rep(mask, 0, 1<<M) if(mask & (1 << i)) SOS[mask] += SOS[mask^(1<<i)]; mint ans = 0; rep(mask, 0, 1<<M){ int cnt = 0; rep(i, 0, M) if((mask & (1 << i)) == 0) cnt++; if(cnt & 1) ans -= (mint(2).pow(SOS[mask])); else ans += (mint(2).pow(SOS[mask])); } cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: 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의 최대 독립 집합의 크기를 구하세요.