글 읽기 - (C++) dp함수의 base case를 이렇게 처리하면 왜 안될까요?

wlgur1023 2년 전 0

base case를 고쳐서 맞긴 하였으나, 틀렸던 부분이 이해되지 않아 질문글을 올립니다.

n개의 블록 목록들을 앞에서부터 쓰거나, 쓰지 않으며 DP함수를 호출하였습니다.

가장 마지막 블록을 쓰는 상황은 곧 가장 처음 블록을 바닥에 쌓는 상황과 일치합니다.

한편, 가장 마지막 블록을 쓸 때, 마지막 블록의 높이(height[n])가 함수가 요구한 높이차(diff)와 일치해야만

제가 정의한 함수인 f(n, diff):: n번째 블록부터 남은 블록들을 볼 때, 높이차가 diff를 만족하는 탑의 최대 높이

의 정의를 만족합니다.

따라서 이때 바닥에 높이가 height[n]인 블록을 처음으로 하나 쌓았다고 생각할 수 있고

탑의 최대 높이가 곧 블럭의 높이이므로 maxSum = height[n]를 반환할 수 있다고 생각했습니다.

이렇게 생각하여 base case를 주석 부분과 같이 작성하였는데 틀렸습니다.

이 base case가 틀린 이유가 무엇일까요?

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int INF = 987654321;

int N;
int height[50 + 1];
int dp[50 + 1][250000 + 1];

/**
 * N번 째 블록부터 볼 때, 높이차가 diff인 경우의 최대 높이 합
 * = N+1번 블록부터 볼 때, 높이차가 diff - height[N], // diff > height[N] 이고, 더 큰 쪽에 쌓음
 *                      or diff + height[N],      // 더 작은 쪽에 쌓음
 *                      or height[N]              // diff < height[N] 이고, 더 작은 쪽에 쌓음
 *                      or diff                   // 아무 쪽에도 쌓지 않음
 * 인 경우의 최대 높이 합 + 각 경우에 따른 갱신된 최대 높이의 변화량
 * 
 * f(N, diff) = max( { height[N] + f(N+1, diff - height[N]), if diff > height[N] } )
 *                   { f(N+1, diff + height[N])                                  }
 *                   { diff + f(N+1, height[N] - diff), if diff < height[N]      }
 *                   { f(N+1, diff)                                              }
 * 
 */
int tallerHeight(int n, int diff){
    int& maxSum = dp[n][diff];
    if(maxSum != -1) return maxSum;

    if(diff > 250000) return maxSum = -INF;
    // 이렇게 하면 틀림! 왜 틀리지?
    // if(n == N-1){ // base case
    //     if(height[n] == diff) return maxSum = height[n];
    //     else return maxSum = -INF;
    // }
    if(n == N){ // base case
        if(diff == 0) return 0;
        else          return -INF;
    }

    maxSum = -INF;
    if(diff >= height[n])
        maxSum = max(maxSum, height[n] + tallerHeight(n+1, diff - height[n]));
    maxSum = max(maxSum, tallerHeight(n+1, diff + height[n]));
    if(diff < height[n])
        maxSum = max(maxSum, diff + tallerHeight(n+1, height[n] - diff));
    maxSum = max(maxSum, tallerHeight(n+1, diff));
    return maxSum;
}

int main(){
    cin >> N;

    for(int i = 0; i < N; i++){
        int n; cin >> n;
        height[i] = n;
    }

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

    int ret = tallerHeight(0, 0);
    cout << (ret > 0? ret : -1);


    return 0;
}

kdh6429 2년 전 0

다이해한건 아나지만.. 마지막 블록을 사용하지 않는 경우도 고려해야 하지않을까요.

댓글을 작성하려면 로그인해야 합니다.