[BAE/<JOON> 문제풀이] 2655. 가장 높은 탑 쌓기

https://www.acmicpc.net/problem/2655

2655번: 가장높은탑쌓기

서론

DP 라서 배낭부터 생각했는데 그래프를 가미한 문제였다. 읽은 순간에는 돌끼리 절대 쌓는 순서가 바뀔 수 없으니 그래프로 짜야겠구나 싶다가도 태그보면 DP라 웰논에 매몰돼버린다. 태그 안보고 풀어야 하는데 골랜디 너무 어려워.. 

풀이

서론에 써놓았듯, 돌끼리는 서로 방향 그래프 관계에 있다. 어떤 돌 위에 쌓을 수 있는 가장 높은 탑을 구하고 그 주춧돌에 대해 다시 재귀적으로 같은 로직을 적용해 답을 구했다. 주의할 점은 돌 a => b => c 순으로 쌓는 것이 가능할 때 a => c 로도 간선이 추가되기 때문에 a에 대한 중복계산이 허용될 경우 연산량이 매우 커진다. b를 추가한 경우가 항상 최적인것이 자명하므로 간선 자체를 제거하는 것이 바람직하나 저 간선 잡으려고 워셜 알고리즘 돌리는게 더 시간 낭비 같았다. 그냥 현재 돌멩이 위에 쌓을 수 있는 돌탑 최대 높이를 저장하고 이미 갱신된 돌에 대해서는 추가연산을 하지 않는 식으로 회피했다. 따라서 점화식은 매우 간단하다.

• DP[i] = i 번째 돌멩이를 주춧돌로 하는 가장 높은 돌탑의 높이

또 추가적으로 돌맹이 쌓은 순서를 출력해야하는데, 최댓값을 갱신할 때 사용한 돌 번호를 현재 돌 인덱스에 기록해놓고 부모를 찾아가며 역순으로 출력하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct bl {
    int i, w, h, g;
};
vector<bl> arr; vector<vector<int>> pd; vector<int> p; vector<int> dp;
int r(int c) {
    int& ret = dp[c];
    if (ret != -1) return ret;
    int mx = 0;
    for (const auto& nx : pd[c]) {
        int s = r(nx);
        if (mx < s) {
            mx = s;
            p[c] = nx;
        }        
    }
    return ret = mx + arr[c].h;
}
int main() {
    int n; cin >> n; arr.resize(n + 1); pd.resize(n + 1); p.resize(n + 1, -1); dp = vector<int>(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].w >> arr[i].h >> arr[i].g;      
        arr[i].i = i;
        for (int j = 1; j < i; j++) {
            if (arr[j].w > arr[i].w && arr[j].g > arr[i].g) {
                pd[j].push_back(i);
            }
            if (arr[j].w < arr[i].w && arr[j].g < arr[i].g) {
                pd[i].push_back(j);
            }
        }
        pd[0].push_back(i);
    }       
    r(0); 
    int nx = 0; int cnt = 0; vector<int> dap;
    while (true) {
        nx = p[nx];
        if (nx == -1) break;
        dap.push_back(nx);
    }
    cout << dap.size() << "\n";
    for (int i = dap.size() - 1; i >= 0; i--) {
        cout << dap[i] << "\n";
    }
    return 0;
}