[백준] 1932번 : 정수 삼각형

문제

 

---

풀이

 

이 문제도 동적계획법의 대표적인 문제 중 하나이다.

대표적인 풀이법에는 위에서 아래로 내려가는 방법과 아래에서 위로 올라가는 방법이 있는데, 후자가 훨씬 코드를 간단하게 짤 수 있다.

 

i번째 줄을 계산한다고 하자. i번째 줄의 0번째(지금은 3)를 갱신하려면

i+1번째 줄의 0번째(7)와 더하거나 i+1번째 줄의 1번째(6)와 더하거나 이다. 둘 중 더 큰 값을 취하면 된다.

 

일반화하면 i번째 줄의 j번째 값을 갱신하려면

i+1번째 줄의 j번째 값과 i+1번째 줄의 j+1번째 값을 비교해 더 큰 값과 더하면 되는 것이다.

 

이를 n-1번째줄부터 1번째 줄까지 반복한 뒤 1번째 줄의 1번째 값을 리턴하면 된다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

int triangle[501][501];

int tri_sum(int n) { //맨아래에서 두번째부터 올라가며 계산
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= i; j++) {
            triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1]);
        }
    }
    return triangle[1][1];
}

int main() {
    int n;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++)
            cin >> triangle[i][j];
    }
    cout << tri_sum(n);
}