백준 1126 : 같은 탑

문제 링크

휴가를 보내고 와서 한동안 뜸했는데 다시 시작해야겠다고 본 문제인데 결국 풀이를 봤다. 풀이를 볼 때마다 느끼지만 항상 내가 생각한 거에서 한 발짝만 더 갔으면 먼가 실마리가 잡힐 수 있었을 거 같은 느낌적인 느낌이 든다. 그게 능력인가. 아무튼 그렇다. 최근에 만들고 싶은 게 생겨서 ps에 쏟는 비중이 좀 줄어들지 싶다. 그래도 하루에 한 문제씩은 풀려고 생각 중인데, 음.. 만들어보면서 봐야지 어떻게 될지 모르겠다 아직은.

사설은 뒤로하고, 이 문제는 dp를 이용해서 해결하는 문제이다.

dp 테이블을 잡을 때, dp[i][j] = i 번째 블록까지 썼을 때, 두 블록의 높이 차이가 j 일 때, 더 높은 블록의 높이의 최댓값으로 잡는다.

이렇게 dp 테이블을 잡으면 i 번 블록에 대해서
1) 더 높은 탑에 추가
2) 더 낮은 탑에 추가
3) 추가 X
라는 3개의 선택지가 존재하게 된다.

dp[i-1][j]가 0이 아닐 때, (vec[i]는 i 번째 블록의 높이)

1)은 dp[i]j + vec[i]] = max(dp[i]j + vec[i]], dp[i-1][j] + vec[i])으로 나타낼 수 있다. (그림을 그려서 보면 편하다)

2)는 더 낮은 탑에 추가함으로써 그 탑의 높이가 역전되는지, 아닌지에 따라서 점화식을 다르게 세워야 한다.

역전되지 않는다면(j >= vec[i]이라면)
dp[i]j-vec[i]] = max(dp[i]j-vec[i]], dp[i-1][j]) 가 되고 - 높은 탑은 그대로이기 때문에 dp[i-1][j] 사용

역전된다면 (j < vec[i]이라면)
dp[i]vec[i]-j] = max(dp[i]vec[i]-j], dp[i-1][j] - j + vec[i]) 가 된다. dp[i-1][j] - j + vec[i]는 더 작은 탑의 높이가 dp[i-1][j] - j였으므로, 여기에 vec[i]를 쌓은 것을 나타낸다.

3)은 dp[i][j] = max(dp[i-1][j], dp[i][j])로 나타낼 수 있다.

같은 탑을 만들 수 없는 경우는 dp[n-1][0] == 0인지 판단함으로써 찾을 수 있다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>
#include <string.h>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const ll INFLL = 1LL << 60;
const int INF = 21*1e8;
const int MAX = 5*1e5;

vector<int> vec;
vector<vector<int>> dp;
int n;

int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin>>n;
    vec = vector<int>(n);
    dp = vector<vector<int>>(n,vector<int>(MAX+1,0));
    
    for(int i = 0;i<n;i++)
    {
        cin>>vec[i];    
    }

    dp[0][vec[0]] = vec[0];
    for(int i = 1;i<n;i++)
    {
        for(int j = 0;j<=MAX;j++)
        {
            if(dp[i-1][j])
            {
                dp[i][j] = max(dp[i][j],dp[i-1][j]);
                if(j + vec[i] <= MAX) dp[i][j+vec[i]] = max(dp[i][j+vec[i]],dp[i-1][j] + vec[i]);

                if(j - vec[i] >= 0) dp[i][j-vec[i]] = max(dp[i][j-vec[i]],dp[i-1][j]);
                else dp[i][vec[i]-j] = max(dp[i][vec[i]-j],dp[i-1][j]-j+vec[i]);
            }
        }

        dp[i][vec[i]] = max(dp[i][vec[i]],vec[i]);        
    }

    cout<<(dp[n-1][0] == 0?-1 : dp[n-1][0]);

}