[백준 1932번] [동적 계획법] 정수 삼각형

Approach

아래쪽으로 내려갈 때, 2가지 가능성이 존재한다.

대각선 왼쪽, 대각선 오른쪽

 

그런데 인덱스를 잘 생각해보면 자신이랑 같은 인덱스이거나 1개 더 작은 값이라는 것을 쉽게 파악할 수 있다.

 

이 점을 이용해보면, 점화식을 세울 수 있다.

추가적으로 자신보다 큰 index의 값은 필요가 없으므로 슬라이딩 윈도우 기법을 활용해서 Space complexity를 조금 더 낮출 수 있기는 하지만 생략..

 

dp[i][j]를 i번째 줄 j번째 index가 가지는 값의 최대값이라고 가정하자.

그러면 점화식은 다음과 같다.

$$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + v \mbox{ (단, i는 줄 넘버, j는 몇번 째 수)$$

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int dp[501][501];
int n;

int dp_return(int row, int index){
    if(index < 1 || index > n) return 0;
    else return dp[row][index];
}

int main(void){
    fastio;
    cin >> n;

    cin >> dp[1][1];

    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++){
            int t;
            cin >> t;
            dp[i][j] = max(dp_return(i - 1, j - 1), dp_return(i - 1, j)) + t;
        }
    }

    int max_value = -1;

    for(int i = 1; i <= n; i++){
        max_value = max(max_value, dp[n][i]);
    }

    cout << max_value << "\n";
    return 0;
}