요즘 DP에 약한 기분이 많이 들어서, 플래티넘 DP 문제 중 특별한 기법이나 최적화를 이용하지 않는 문제들을 푼 사람 수로 정렬해서 안 푼 문제들을 선별하여 조금씩 풀고 있다. 푼 사람 수로 정렬한 문제라 이미 남들에겐 웰논일지도 모른다.
많이 풀린 문제들답게 플래티넘임에도 불구하고 꽤 잘 풀리는 것도 있는 반면 해설 없이는 못 풀었을 문제들도 많았다. 아마 DP라는 걸 모르고 풀었다면 체감 난이도가 훨씬 높았을 것 같다.
[BOJ 1126] 같은 탑 (Platinum III)
N = 50개의 블록을 이용하여 높이가 같은 두 개의 탑을 만든다. 모든 블록을 사용할 필요는 없으며, 각 블록의 높이는 최대 50만이고, 모든 블록의 높이의 합이 50만 이하이다.
이때, 만들 수 있는 탑의 높이의 최댓값을 구하는 문제이다.
풀이)
풀이를 떠올리기가 어려운 문제이다. 다른 블로그의 해설을 참고하여 해결했다.
먼저, 두 탑을 A, B라고 한다면 각 블록은 A에 속하거나, B에 속하거나, 혹은 버려지게 되는 총 3가지의 경우를 갖는다. 따라서 새로운 블록을 추가할 때마다 각 탑에 속해있는 블록들의 상태를 저장하기에는 N이 최대 50이기 때문에 어렵다. 반대로 각 탑의 높이를 저장하기엔 탑의 높이가 최대 25만이기 때문에 25만 * 25만의 배열이 필요하므로 이 또한 어렵다.
핵심적인 아이디어는 두 탑을 각각 저장하지 않고 '두 탑의 높이의 차'만 저장해 나간다.
dp table은 다음과 같이 정의한다.
dp[i][j] = i번째 블록까지 이용하고 두 탑의 높이 차가 j일 때 두 탑의 높이 중 더 큰 값
그러면 최종적으로 구하는 답은 dp[n][0]이 된다.
점화식은 어떻게 될까? 현재 i번째 블록까지 사용했고 두 탑의 높이 차가 d라고 하고, i+1번째 블록의 높이가 a[i+1]이라고 하자. i+1번째 블록을 이용하는 경우는 다음과 같다.
1. 두 탑 중 더 높은 탑에 쌓기
2. 두 탑 중 더 낮은 탑에 쌓기
3. 사용하지 않기
두 탑 중 더 높은 탑에 쌓는 경우는 두 탑의 높이 차가 a[i+1]만큼 커지게 되며, d 또한 a[i+1]만큼 더 커지게 된다.
따라서 dp[i+1][d+a[i+1]] = max(dp[i+1][d+a[i+1]], dp[i][d] + a[i+1])을 만족한다.
두 탑 중 더 낮은 탑에 쌓는 경우는 d가 a[i+1]이상인지 미만인지에 따라 달라진다.
d >= a[i+1]인 경우에는 낮은 탑에 쌓으면 a[i+1]만큼 d가 줄어들게 되고, 두 탑 중 최댓값은 유지된다.
반대로 d < a[i+1]인 경우는 낮은 탑에 쌓으면 해당 탑이 더 높은 탑이 되어버리고, d는 a[i+1] - d 가 된다. 두 탑 중 최댓값은 a[i+1] - d만큼 증가하게 된다.
따라서 d >= a[i+1]인 경우는 dp[i+1][d - a[i+1]] = max(dp[i+1][d-a[i+1]], dp[i][d])이며,
d < a[i+1]인 경우는 dp[i+1][a[i+1] - d] = max(dp[i+1][a[i+1]-d], dp[i][d] + a[i+1] - d)가 된다.
i+1번째 블록을 사용하지 않는 경우는 dp[i+1][d] = max(dp[i+1][d], dp[i][d])를 만족한다.
코드)
#include<bits/stdc++.h>
#define ini(x, y) memset(x, y, sizeof(x));
using namespace std;
int dp[51][250505];
int n, a[51];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
ini(dp, -1);
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
int k = a[i + 1];
for (int j = 0; j <= 250000; j++) {
if (dp[i][j] == -1) continue;
if (j + k <= 250000) dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + k);
if (k <= j) dp[i + 1][j - k] = max(dp[i + 1][j - k], dp[i][j]);
else if (k - j <= 250000) dp[i + 1][k - j] = max(dp[i + 1][k - j], dp[i][j] + k - j);
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
}
}
if (dp[n][0] <= 0) cout << -1;
else cout << dp[n][0];
}
[BOJ 1028] 다이아몬드 광산 (Platinum V)
R = 750, C = 750인 2차원 배열에서 1로 이루어진 다이아몬드 모양의 최대 크기를 구하는 문제이다. 다이아몬드 모양은 다음과 같다.
풀이)
이 문제 또한 해설을 참고하여 풀었다.
처음엔 다이아몬드의 크기를 점점 키워가면서 더 작은 다이아몬드로 큰 다이아몬드를 만들 수 있는지를 체크하는 방식으로 해결하려고 했으나, 다이아몬드 내부는 0이어도 상관없는 부분 때문에 잘 되지 않았다.
핵심 아이디어는, 현재 (x, y)를 다이아몬드의 윗 꼭짓점이라고 했을 때 얼마나 큰 다이아몬드가 만들어질 수 있는지를 확인하는 것이다.
이를 위해서 현재 정점에서부터 네 대각선으로 1이 최대 얼마나 연속되어 있는지를 dp를 이용하여 저장해두면, 윗 꼭짓점과 아랫 꼭짓점 두 점을 잡았을 때 다이아몬드가 만들어질 수 있는지를 O(1)만에 체크할 수 있다.
코드)
#include<bits/stdc++.h>
using namespace std;
int a[800][800];
int ur[800][800], ul[800][800], dr[800][800], dl[800][800];
int main(void) {
int r, c; cin >> r >> c;
for (int i = 1; i <= r; i++) {
string s; cin >> s;
for (int j = 1; j <= c; j++) {
a[i][j] = s[j - 1] - '0';
}
}
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (a[i][j] == 1) {
ur[i][j] = ur[i - 1][j + 1] + 1;
ul[i][j] = ul[i - 1][j - 1] + 1;
}
}
}
for (int i = r; i >= 1; i--) {
for (int j = 1; j <= c; j++) {
if (a[i][j] == 1) {
dr[i][j] = dr[i + 1][j + 1] + 1;
dl[i][j] = dl[i + 1][j - 1] + 1;
}
}
}
int ans = 0;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
for (int k = min(dl[i][j], dr[i][j]); k >= ans + 1; k--) {
if (ul[i + 2 * (k - 1)][j] >= k && ur[i + 2 * (k - 1)][j] >= k) {
ans = max(ans, k);
break;
}
}
}
}
cout << ans;
}
[BOJ 1135] 뉴스 전하기 (Platinum V)
트리가 있고, 루트부터 시작해서 뉴스를 전달한다. 각 정점은 한 번에 한 자식에게 뉴스를 전달하며, 뉴스를 전달할 땐 1분의 시간이 걸린다. 이때, 모든 정점에게 뉴스가 전달되기 위한 최소 시간을 구해야 한다.
풀이)
DP 같으면서도 사실 DP 없이 해결 가능하다. 예를 들어 자식 정점이 3개 (a, b, c)가 있다고 하자.
a -> b -> c 순서대로 뉴스를 전달하면 c를 루트로 하는 서브 트리의 정점들은 모두 전달받는 시간이 a보다 2초 더 걸린다. 하지만 만약 c에서부터 자손으로 뉴스를 전달하는 시간이 a에서부터 전달하는 시간보다 더 크다면, c->a->b와 같이 a보다 c에 먼저 전달하는 것이 더 이득이다.
모든 정점에 뉴스가 전달되기 위한 시간이 최소가 되어야 하기 때문이다.
따라서 현재 노드를 u라고 하고, 자식 노드들을 v1, v2, ... 라고 하면, vi를 루트로 하는 서브 트리에서 모든 정점에 뉴스가 전달되기 위한 시간을 내림차순으로 정렬한 다음, 순서대로 먼저 뉴스를 전달한다.
코드)
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
using namespace std;
vector<int> adj[51];
int dfs(int u) {
if (sz(adj[u]) == 0) {
return 0;
}
vector<int> vc;
for (int v : adj[u]) {
vc.pb(dfs(v));
}
sort(all(vc), greater<int>());
int mx = 0;
for (int i = 0; i < sz(vc); i++) {
mx = max(mx, vc[i] + i + 1);
}
return mx;
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n; cin >> n;
for (int i = 0; i < n; i++) {
int a; cin >> a;
if (a != -1) adj[a].pb(i);
}
cout << dfs(0);
}
[BOJ 5573] 산책 (Platinum IV)
가로로 H개, 세로로 W개의 도로로 이루어진 산책로가 존재하고, 각 교차로마다 오른쪽으로 이동하는지 아래쪽으로 이동하는지 초깃값이 주어진다.
산책로의 밖으로 나가면 산책이 종료되고, 한번 교차로를 지나면 해당 교차로의 방향은 반대가 된다. 즉, 오른쪽이었으면 아래쪽으로, 아래쪽이었으면 오른쪽으로 바뀐다.
N-1번의 산책이 끝난 후, N번째 산책을 할 때 산책이 종료되었을 때의 위치를 하는 문제이다. (N = 10^7)
풀이)
기본적으로 N이 최대 10^7이므로, 매번 산책을 하면서 방향을 직접 바꿔줄 수는 없다.
단, 교차로의 방향은 해당 교차로를 몇 번 방문했는지에 따라서 달라지므로 N번째 산책 이전까지 각 교차로의 방문 횟수를 구하면 N번째 산책의 도착지점을 알 수 있다.
따라서, dp table을 dp[i][j] = 교차로 (i, j)를 방문한 횟수로 정의한다.
(1, 1)은 시작점이므로 항상 방문하기 때문에 dp[i][j] = N-1이다.
현재 위치를 (x, y)라고 하면, 항상 오른쪽 또는 아래쪽으로 이동하기 때문에 (x-1, y)와 (x, y-1)만 체크하면 된다.
(x-1, y)의 초깃값을 0이라고 하고, (x-1, y)를 k번 방문했다고 가정하자. 그러면 (x-1, y)에서 (x, y)로 (k+1)/2번 이동할 것이다.
반대로 (x-1, y)의 초깃값을 1이라고 하면 (x-1, y)에서 (x, y)로 k/2번 이동할 것이다.
즉, 초기 방향에 따라서 더해지는 값이 달라지게 되는 것이다.
최종적으로 N번째 산책하기 전의 교차로의 상태를 만들어둔 다음 N번째는 직접 이동시켜서 도착점을 찾아주면 된다.
코드)
#include<bits/stdc++.h>
using namespace std;
int A[1010][1010];
int dp[1010][1010];
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int h, w, n; cin >> h >> w >> n;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> A[i][j];
}
}
dp[1][1] = n - 1;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (i > 1) dp[i][j] += (A[i - 1][j] == 0 ? (dp[i - 1][j] + 1) / 2 : dp[i - 1][j] / 2);
if (j > 1) dp[i][j] += (A[i][j - 1] == 1 ? (dp[i][j - 1] + 1) / 2 : dp[i][j - 1] / 2);
}
}
int x = 1, y = 1;
while (x <= h && y <= w) {
if ((A[x][y] + dp[x][y]) % 2) y++;
else x++;
}
cout << x << ' ' << y << '\n';
}
[BOJ 2315] 가로등 끄기 (Platinum III)
최대 1000개의 가로등이 0부터 1000까지의 위치에 일렬로 나열되어 있고, 각 가로등마다 매초 소비하는 전력의 양이 주어진다. 만약 가로등이 s초동안 켜져 있고, 매 초 w만큼 전력을 소비한다면 총 s*w만큼 전력이 소비된다.
현재 위치한 가로등의 번호가 주어지고, 1초에 1만큼 움직이면서 만나는 가로등을 끌 때, 모든 가로등을 끄기 위한 최소 소비 전력량을 구하는 문제이다. (가로등을 끄는데 걸리는 시간은 없다)
풀이)
현재 위치한 가로등 번호를 m이라고 하자.
가로등을 끄는데 필요한 시간이 없기 때문에 예를 들어 m -> m-4번째 가로등으로 이동하는 것과 m -> m-1 -> m-2 -> m-3 -> m-4번째 가로등으로 차례대로 이동하는 것은 동일하다.
m -> m-4번째 가로등으로 이동하면서 만나는 가로등은 모두 꺼버리기 때문이다.
따라서 지금까지 끈 가로등의 범위를 [l, r]이라고 하면 항상 l-1 또는 r+1로만 이동시키면서 확인해도 충분하다.
그러므로 dp table을 dp[l][r][k] = [l, r] 범위의 가로등이 꺼져있을 때 나머지 가로등을 끌 때까지 소비되는 최소 전력으로 정의한다. 그리고 k는 현재 l에 위치해있는지, r에 위치해있는지를 나타내는 0 또는 1의 값이다.
이제, l-1 또는 r+1로 이동시키는데, 이동하는 과정에서 이동하는 거리 * 켜져 있는 가로등의 소비 전력의 합만큼 전력이 더 소모되게 된다.
가로등의 소비 전력을 누적합으로 계산을 해두면, 켜져있는 가로등의 소비 전력의 합 = Total - (psum[r] - psum[l-1])으로 쉽게 구할 수 있다.
코드)
#include<bits/stdc++.h>
#define ini(x, y) memset(x, y, sizeof(x));
using namespace std;
using pii = pair<int, int>;
const int MAX = (int)1e9;
int dp[1010][1010][2];
int psum[1010];
int n, m;
pii a[1010];
int sol(int l, int r, int pos) {
if (l == 1 && r == n) return 0;
int &ret = dp[l][r][pos];
if (ret != -1) return ret;
ret = MAX;
int R = psum[n] - (psum[r] - psum[l - 1]);
int now = (pos == 0 ? a[l].first : a[r].first);
if (l > 1) ret = min(ret, sol(l - 1, r, 0) + R * (now - a[l - 1].first));
if (r < n) ret = min(ret, sol(l, r + 1, 1) + R * (a[r + 1].first - now));
return ret;
}
int main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
ini(dp, -1);
for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
psum[i] = psum[i - 1] + a[i].second;
}
cout << sol(m, m, 0);
}
PC로 보시는 것을 권장합니다.
피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
| [BOJ 1396] 크루스칼의 공 (2) | 2021.06.10 |
|---|---|
| [BOJ 20190] 버블버블 (3) | 2020.12.28 |
| [BOJ 17353] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 (2) | 2020.12.22 |
| [BOJ 7812] 중앙 트리 (2) | 2020.12.14 |
| [BOJ 9202] Boggle (0) | 2020.12.13 |
