[BOJ_C++] 1932번 : 정수 삼각형

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

int dp[500][500] = { 0 };
int tree[500][500] = { 0 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> tree[i][j];
            dp[i][j] = tree[i][j];
        }
    }

    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = (dp[i + 1][j] > dp[i + 1][j + 1]) ? dp[i + 1][j] + tree[i][j] : dp[i + 1][j + 1] + tree[i][j];
        }
    }

    printf("%d", dp[0][0]);

    return 0;
}

• 맨 위층부터 시작하여 아래에 있는 수 중 대각선 왼쪽 또는 대각선 오른쪽에 있는 것과의 최대 합을 구하는 것은 크기가 2인 삼각형의 맨 아래층 수 중 왼쪽 또는 오른쪽 값 중 더 큰 값을 맨 위층 수와 더하는 것의 반복이다.

i층 j번째 값
i+1층 j값	i+1층 j+1 값

• 다시말해 dp i층의 j번째 값을 구하기 위해서는 dp i+1층의 j값과 j+1값 중 더 큰 값을 tree i층 j번째 값과 더해주면 된다.
• 최종적으로 구해진 dp[0][0]의 값은 최대 합을 구한 것과 같다. 따라서 dp[0][0]을 출력하고 프로그램을 종료한다.

결과