[BOJ / DP] 1126 같은탑

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

1126번: 같은 탑

 

1126 같은 탑

알고리즘 : DP

일반적인 dp 구조로는 풀이를 떠올리기 힘든 문제입니다. 보고나서 경찰차 문제가 떠올랐지만 그 방식으로도 해결이 되지 않았습니다. 2차원 dp 테이블을 구상하여야 하는데 dp[A][B]=K

 

                                                      -   A : A-1번째까지의 블록을 사용하였을 때

                                                      -   B : 각 탑의 높이가 차이가 B일 때

                                                      -   K : 둘 중 더 높은 탑의 높이

입니다.

이를 이용해 i번째 블록을 안 사용하는 것과, 더 큰 쪽에 놓는 것, 더 작은 쪽에 놓는 것 세 개를 bottom up 방식으로 구하면 결과 값을 구할 수 있습니다.

 

 

 

< CODE >

#include <iostream>

using namespace std;

#define MAX 55

int h[MAX];
int dp[MAX][500005];
int result = 0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    int sum = 0;

    cin >> n;
    
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
        sum += h[i];

        for (int j = 1; j <= 500000; j++)
            dp[i][j] = -1;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= sum; j++)
        {
            if (dp[i][j] == -1)
                continue;

            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            dp[i + 1][j + h[i]] = max(dp[i + 1][j + h[i]], dp[i][j] + h[i]);

            if (j > h[i])
                dp[i + 1][j - h[i]] = max(dp[i + 1][j - h[i]], dp[i][j]);
            else if (j == h[i])
            {
                dp[i + 1][0] = max(dp[i + 1][0], dp[i][j]);
                result = max(result, dp[i][j]);
            }
            else if (j < h[i])
                dp[i + 1][h[i] - j] = max(dp[i + 1][h[i] - j], dp[i][j] + h[i] - j);
        }
    }

    if (result == 0)
        cout << "-1\n";
    else
        cout << result << '\n';

    return 0;
}

시간 : 100ms

 

태그 : #BOJ 같은탑 #백준 같은탑 #1126 같은탑 #같은탑 풀이