[백준,c++] 1932번 - 정수 삼각형

문제

1932번: 정수 삼각형

코드

#include <iostream>

using namespace std;

int arr[501][501];
int dp[501][501];
int ans;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N; cin>>N;
    for(int i=1; i<=N; i++){
        for(int k=0; k<i; k++){
            cin>>arr[i-1][k];
        }
    }
    dp[0][0] = arr[0][0];
    ans = dp[0][0];
    
    for(int i=1; i<N; i++){
        for(int k=0; k<N; k++){
            if(k==0) dp[i][k] = dp[i-1][k] + arr[i][k];
            else if(k==N-1) dp[i][k] = dp[i-1][k-1] + arr[i][k];
            else dp[i][k] = max(dp[i-1][k-1]+arr[i][k],dp[i-1][k]+arr[i][k]);
            ans = max(ans, dp[i][k]);
        }
    }
    cout<<ans;
    
}

 

풀이

 현재 층의 위 쪽의 왼쪽 또는 대각선 오른쪽에 있는 것 중에서 선택하여 만들어 낼 수 있는 가장 큰 수를 출력하는 것입니다.

                  7
               3   8
             8   1   0
           2   7   4   4
        4   5   2   6   5

하지만 입력은 아래와 같이 주어집니다.

5

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

따라서 아래와 같은 점화식을 세워 맨 처음과 맨 끝 그리고 나머지 일 때의 경우를  나누어 점화식을 세워 해결할 수 있습니다.

if(k==0) dp[i][k] = dp[i-1][k] + arr[i][k];
else if(k==N-1) dp[i][k] = dp[i-1][k-1] + arr[i][k];
else dp[i][k] = max(dp[i-1][k-1] + arr[i][k], dp[i-1][k] + arr[i][k]);