백준 1932. 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

이전에 푼 RGB거리와 아주 유사해서 쉽게 푼 문제. (tose33.tistory.com/106)

 

 

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다,

 

d[n][0] : n층 0번째 요소를 선택했을때 합의 최댓값.

d[n][1] : n층 1번째 요소를 선택했을때 합의 최댓값.

 

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있으므로,

이전 층의 좌측과 우측에 있는 수 중 큰값에, 현재 값을 더하면 된다.

 

예를들어, d[4][1]을 구한다고 하면,

d[3][0](18)과 d[3][1](16) 중 큰 값에 tri[4][1](7)을 더하면 된다.

 

tri[]

d[]

 

 

#include <iostream>
using namespace std;
#include <algorithm>

int tri[501][501];
int d[501][501];

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

    // triangle input
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            cin >> tri[i][j];
        }
    }

    d[1][0] = tri[1][0];

    // bottom-up
    for(int i = 2; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            if(j == 0) { // 첫 요소
                d[i][j] = d[i-1][0] + tri[i][0];
            }
            else if(j == i-1) { // 마지막 요소
                d[i][j] = d[i-1][j-1] + tri[i][j];
            }
            else { // 가운데 요소
                d[i][j] = max(d[i-1][j-1], d[i-1][j]) + tri[i][j];
            }
        }
    }

    cout << *max_element(d[n], d[n]+n+1);
}