1932: 정수 삼각형

• toc {:toc}

문제 확인하기

풀이

최댓값을 찾을 수 있는 삼각형의 규칙을 생각해본다.

위에서부터 맨 마지막 층까지 내려가면서 선택할 수 있는 값 중 높은 값을 더해주면 맨 마지막에 있는 값은 각 루트로 더할 수 있는 최댓값이 된다.

때문에 맨 마지막 층의 값 중 최댓값을 구하면 해당 값이 최대가 되는 경로에 있는 수의 합이다.

• 예시 7
  3 8
  8 1 0
  2 7 4 4
  4 5 2 6 5

누적합 예시
dp[1][0] = dp[0][0] + dp[1][0] = 7 + 3, dp[1][1] = dp[0][0] + dp[1][1] = 7 + 8
dp[2][0] = dp[1][0] + dp[2][0] = 7+3+8, dp[2][2] = dp[1][1] + dp[2][2] = 7+8+0
dp[2][1] = max(dp[1][0], dp[1][1]) + dp[2][1] ...

즉, 왼쪽, 오른쪽 가장자리에 위치한 경우 내가 넘겨 받을 수 있는 값이 한 가지 밖에 없고, 중간에 위치한 경우 왼쪽 대각, 오른쪽 대각의 값을 넘겨 받을 수 있기 때문에 둘 중 큰 값으로 넘겨 받아 최대 경로를 찾는다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
 
int dp[501][501] = {0,};
int n, maxNum=0;
 
int main(){
    ios::sync_with_stdio(false);
    using namespace std;
 
    cin >> n;
 
    int val;
    for(int i=0; i<n; i++){
        for(int j=0; j<=i; j++){
            cin >> val;
            dp[i][j] = val;
        }
    }
 
    if(n == 1){
        cout << dp[0][0];
        exit(0);
    }
 
    for(int depth=1; depth<n; depth++){
        for(int idx=0; idx<=depth; idx++){
            if(idx == depth)
                dp[depth][idx] = dp[depth-1][idx-1] + dp[depth][idx];
            else if(idx == 0)
                dp[depth][idx] = dp[depth-1][idx] + dp[depth][idx];
            else
                dp[depth][idx] = max(dp[depth-1][idx], dp[depth-1][idx-1]) + dp[depth][idx];
            
            maxNum = max(maxNum, dp[depth][idx]);
        }
    }
 
    cout << maxNum << '\n';
 
    return 0;
}