[백준 1932번] 정수 삼각형

문제 링크: https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

<문제 풀이> 다이나믹 프로그래밍(DP)

[테이블을 정의]

d[i][j] = i번째 층으로 갈 때 i번째 층에 있는 수들 중에서 j번째 수로 가는 경로의 합의 최대

[점화식 정의]

d[i][j] = 왼쪽 위 대각선의 숫자를 고려해서 d[i][j]로 가는 경로의 합과 오른쪽 위 대각선의 숫자를 고려해서 d[i][j]로 가는 경로의 합의 최댓값 + d[i][j]

d[i][j] += max(d[i-1][j-1], //  왼쪽 위 대각선
                   d[i-1][j]); // 오른쪽 위 대각선

<C++ 소스 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int n;
int d[501][501];
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> d[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            d[i][j] += max(d[i - 1][j - 1], d[i - 1][j]);
            
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, d[n][i]);
    }
    cout << res;
 
}