[BOJ 1932] 정수 삼각형

 

1932번: 정수 삼각형

1. 문제 설명

위 예제이서는 7 - 3 - 8 - 7 - 5 를 선택했을 때가 최대가 되는 경로이므로, 수들의 합인 30을 출력한다.

 

2. 구현 아이디어 1 - 맞았습니다 !!

DP가 적용될 수 있는 조건은

1. 동일한 작은 문제들이 반복하여 나타나는 경우
2. 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 나타낼 수 있는 경우

이다.

 

윗 줄에서 구한 합을 현재 줄에서의 최댓값을 구하는데 사용하며(1번 조건 충족), 윗 줄에서 구한 합에 따라 현재 줄에서의 수의 합이 달라지므로(2번 조건 충족) DP를 사용해서 풀 수 있다.

 

DP 배열은 입력과 동일하게 2차원 배열을 사용한다.

이제 일반화를 하기 위해 규칙을 찾아보자. 정수 삼각형에서 DP 값(=현재까지 지나온 경로의 수의 합의 최댓값)은 3가지 경우로 나누어 구할 수 있다.

1. 왼쪽 변에 있는 경우 - 자신의 오른쪽 대각선 위에 있는 수만 고를 수 있다.
2. 오른쪽 변에 있는 경우 - 자신의 왼쪽 대각선 위에 있는 수만 고를 수 있다.
3. 나머지 경우 - 자신의 왼쪽, 오른쪽 대각선 위에 있는 수 중 더 큰 값을 고른다.

 

처음에는 삼각형 모양이길래 모양 그대로 2차원 배열에 담는 것이 어렵다고 생각하여 아래 사진처럼 몇 층에 있는 숫자인지 구하고, 층수와 연관된 규칙을 찾으려고 했다.

 

하지만 층수를 구하는 과정이 반복되며 로직이 복잡해졌고, 다른 방법을 찾았다.

바로 입력 받은 그대로 저장하는것이다!

 

그렇게 된다면 행을 i, 열을 j로 했을 때 왼쪽 대각선 위의 수는 dp[i-1][j], 오른쪽 대각선 위의 수는 dp[i-1][j-1]로 나타낼 수 있다.

이렇게 입력을 받으면 점화식을 아래와 같이 정할 수 있다.

 

아래 코드에서 board는 입력받은 2차원 배열이다.

// 왼쪽 변에 있는 경우
dp[i][j] = dp[i-1][j] + board[i][j];

// 오른쪽 변에 있는 경우
dp[i][j] = dp[i-1][j-1] + board[i][j];

// 나머지 경우
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + board[i][j];

 

2중 반복문을 돌며 정수 삼각형을 순회하면, DP 배열의 가장 마지막 행에 선택된 수들의 합이 저장되어 있을 것이다.

그러므로 그 중 가장 큰 값을 선택하면 최종적으로 합이 최대가 되는 경로의 수들의 합을 구할 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

int n;
int ret;
int board[500][500];
int dp[500][500];

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            cin >> board[i][j];
        }
    }

    dp[0][0] = board[0][0];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j == 0) dp[i][j] = dp[i-1][j] + board[i][j];
            if (j == i) dp[i][j] = dp[i-1][j-1] + board[i][j];
            else dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + board[i][j];
        }
    }

    for (int i = 0; i < n; ++i) {
        if (dp[n-1][i] > ret) ret = dp[n-1][i];
    }

    cout << ret << endl;

    return 0;
}