백준 1126번 같은 탑

문제 링크입니다: https://www.acmicpc.net/problem/1126

처음 보는 유형의 DP 문제였습니다.

확실히 DP 카테고리 첫 페이지 끝에서부터는 능력자분들의 블로그 도움 없이는 못 푸는 것 같습니다 ㅠㅠ

더 열심히 공부하면서 내공을 쌓아야겠다고 느낀 문제였습니다.

아래 알고리즘은 junodeveloper님(http://junh0.tistory.com/2)의 포스팅을 참고했습니다.

junodeveloper님의 블로그에 그림과 함께 상세한 설명이 적혀있기 때문에 링크 참고하시는 것을 추천드립니다!

각 나무 블럭마다 4가지 경우의 수를 고려해줘야합니다.

1. 해당 블럭을 쓰지 않을 경우

2. 해당 블럭을 더 높은 탑에 쌓는 경우

3. 해당 블럭을 더 낮은 탑에 쌓는 경우

i) 해당 블럭이 탑 간의 높이차보다 클 경우

ii) 해당 블럭이 탑 간의 높이차보다 작을 경우

또한, 탑 간의 높이 차가 초과하거나 마지막 조각까지 사용했는데도 높이차가 존재한다면 성립하지 않는 경우라고 계산해야합니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 50;

const int INF = 987654321;

 

int N;

int arr[MAX];

//모든 조각의 높이의 합은 500,000을 넘지 않고 탑은 두개

int cache[MAX][500000 / 2 + 1]; //idx, height Difference

 

int maxHeight(int idx, int heightDiff)

{

        //기저 사례: 높이 차 초과, 높이가 같지 않은 상태에서 범위 초과

        if (heightDiff > 500000 / 2)

                 return -INF;

        if (idx == N && heightDiff)

                 return -INF;

       

        //높이가 동일하다면 조건 충족

        if (idx == N && heightDiff == 0)

                 return 0;

 

        int &result = cache[idx][heightDiff];

        if (result != -1)

                 return result;

 

        result = -INF;

        //idx 번쨰 조각을 쓰지 않음

        result = max(result, maxHeight(idx + 1, heightDiff));

        //idx 번째 조각을 높은 탑에 배치

        result = max(result, maxHeight(idx + 1, heightDiff + arr[idx]));

        //idx 번째 조각을 낮은 탑에 배치

        //해당 조각이 두 탑의 높이 차보다 큰 경우

        if (arr[idx] > heightDiff)

                 result = max(result, heightDiff + maxHeight(idx + 1, arr[idx] - heightDiff));

        //idx 번째 조각이 두 탑 높이 차보다 작거나 같은 경우

        else

                 result = max(result, arr[idx] + maxHeight(idx + 1, heightDiff - arr[idx]));

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i];

 

        memset(cache, -1, sizeof(cache));

        int result = maxHeight(0, 0);

       

        if (result)

                 cout << result << "\n";

        else

                 cout << -1 << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~