백준 1126 같은 탑

DP 문제를 슥 보다가 오우 문제 짧네? 하고 한번 잡아봤다. 근데 플은 괜히 플이 아니더라... 하하...

 

처음 접근했을때, dp[i]를 i 높이로 탑을 쌓을 수 있는 조건으로 접근했다.

dp[i]는 벡터였고, dp[2]는 2 높이를 만들 수 있는 블럭들 상태들을 저장하고 있었다. 루프 돌면서 이전 조합에 지금 블럭을 or 해서 추가하고, dp[i]가 2 이상인 경우 중 최대값을 출력했다.

답은 나왔는데 예상보다 루프가 많아 시간 초과가 떴다.

 

시간 갈아넣었는데 시간초과가 나와 좀 더 생각해보다가 검색을 좀 해봤다. dp 배열을 진짜 신박하게 잡더라.

dp[i][j] = i 번째 블럭까지 썼을때, 두 블럭 높이 차이가 j일 경우 두 탑 중 높은 것의 높이. 로 정의해둔다.

이렇게 되면, i와 j를 늘려가며 탐색을 할 경우,

i 번째 블럭에 대해, 더 높은 탑에 추가, 더 낮은 탑에 추가, 추가하지 않는 선택이 가능하다.

각 조건에 대해 디테일한 점화식을 보면,

 

1. 높은 탑에 추가 : 차이가 커진다(j) : dp[i][j + block[i]] = max(dp[i][j + block[i]], dp[i - 1][j] + block[i])

2. 낮은 탑에 추가, 이 경우 두 탑의 순서가 뒤바뀔 수 있다.

2.1. 낮은 탑에 추가되는데, 안뒤집힐때 : dp[i][j - block[i]] = max(dp[i][j - block[i]], dp[i - 1][j])

2.2. 낮은 탑에 추가되는데, 순서가 뒤집힐 때 : dp[i][block[i] - j] = max(dp[i][block[i] - j], dp[i - 1][j] - j + block[i]) // dp[i - 1][j] 에서 작은 탑은 dp[i - 1][j] - j 이므로.

3. 선택 안하는 경우 :  dp[i][j] = max(dp[i - 1][j], dp[i][j])

 

이렇게 쪼개진다.

진짜 어떻게 이렇게 접근하는지 모르겠다. 문제보고 이걸 이렇게 한번에 생각한다고? 이게 어떻게 된다는거야...

 

이 루프를 다 돌며 dp 배열을 채우고 난 뒤, dp[n-1][0]을 확인하면 답이다.

---

#include <iostream>
#include <vector>
int main()
{
    int n;
    std::cin >> n;

    int block[n];
    int max = 0;
    for (int i = 0; i < n; i++)
    {
        std::cin >> block[i];
        max += block[i];
    }
    
// dp[i][j] = i 번째 블록까지 썼을때, 두 블록 높이 차이가 j일때 두 탑 높이 중 큰 것.
// i 번째 블록에 대해, 더 높은 탑에 추가, 더 낮은 탑에 추가, 추가 X 선택지.
// 1. 차이가 커진다(j) : dp[i][j + block[i]] = max(dp[i][j+ block[i]], dp[i-1][j] + block[i])
// 2. 차이가 줄어드는데, 두 탑의 높이가 역전될수도 있음
// 2.1. 역전되지 않는 경우(j >= block[i]) : dp[i][j - block[i]] = max(dp[i][j - block[i]], dp[i-1][j])
// 2.2. 역전되는 경우 (j < block[i]) : dp[i][block[i] - j] = max(dp[i][block[i] - j], dp[i-1][j] -j + block[i])
// 3. 선택 안하는 경우 : dp[i][j] = max(dp[i-1][j], dp[i][j])

    std::vector<std::vector<int>> dp(n, std::vector<int>(max + 1, 0));

    dp[0][block[0]] = block[0];

    for(int i = 1; i < n ; i++)
    {
        for (int j = 0; j <= max; j++)
        {
            if (dp[i-1][j]) // 이전블럭 사용한것중, diff 가 j 인 값이 있으면
            {
                dp[i][j] = std::max(dp[i][j], dp[i-1][j]); // 선택 안한 경우

                if(j + block[i] <= max) //높은 곳에 쌓는데, 최대 안넘을때만
                    dp[i][j + block[i]] = std::max(dp[i][j + block[i]], dp[i - 1][j] + block[i]);
                
                if(j - block[i] >= 0) // 낮은 곳에 쌓는데, 안뒤집힐때
                    dp[i][j - block[i]] = std::max(dp[i][j - block[i]], dp[i - 1][j]);
                else // 낮은 곳에 쌓는데, 뒤집힐때
                    dp[i][block[i] - j] = std::max(dp[i][block[i] - j], dp[i - 1][j] - j + block[i]);
            }
        }
        dp[i][block[i]] = std::max(dp[i][block[i]], block[i]); // 위에서 아무것도 처리 안됬을 경우, i블럭 하나만 써서 탑 한개 만든 상태 정의
        // int t1 = dp[i][block[i]];
        // int t2 = block[i];
    }

    if (dp[n-1][0])
        std::cout << dp[n-1][0];
    else
        std::cout << -1;


    //dp[i] = i 값으로 가능한 블럭 조합(long 형, bitmask)
    // std::vector<std::vector<long>> dp(max);
    // max = 0;
    // for (int i = 1; i < dp.size(); i++)
    // {
    //     long mask = 0;
    //     int count = 0;
    //     for (int j = 0; j < n; j++)
    //     {
    //         long curBlock = block[j];
    //         if (curBlock == i)
    //         {
    //             mask = (1 << (j));
    //             for (long i_mask : dp[i])
    //                 if ((i_mask & mask) == 0)
    //                     count++;
    //             dp[i].push_back(mask);
    //         }
    //         else
    //         {
    //             long remain = i - curBlock;
    //             if (remain > 0 && dp[remain].size() != 0)
    //             {
    //                 for (long remain_mask : dp[remain])
    //                 {
    //                     mask = (1 << (j));
    //                     if(mask & remain_mask != 0)
    //                         continue;
    //                     mask = remain_mask | mask;
    //                     for (long i_mask : dp[i])
    //                         if ((i_mask & mask) == 0)
    //                             count++;
    //                     dp[i].push_back(mask);
    //                 }
    //             }
    //         }
    //     }
    //     if (count)
    //         max = i;
    // }
    // if (max)
    //     std::cout << max;
    // else
    //     std::cout << -1;
}

삽질을 한것까지 넣어두니까 엄청 길다. 근데 dp 코드는 진짜 단순하다. DP문제는 너무 허무? 허탈하다. 아직 dp가 어려운 나에게는 접근을 어떻게 하는지 찾고, 오 이렇게 하는구나 까지의 과정이 너무 긴데 코드가 너무 단순하다... 허허...

그래도 좀 신기했다. dp 배열 식이 분기되는것도 참 어쩜 저렇게 딱 맞게 분기가 되는지... dp 배열 의미도 어쩜 저렇게 문제가 원하는 것을 딱 저장하게 구현하는지. 각 행과 열이 의미하는것을 생각해내는게 어려운 것 같다. 신-박

 

오늘도 평온한 하루가 되길. 슨민.