[동적 계획법 1] [C++] 1932번. 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

 

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

---

해결 방법

이전 문제였던 RGB 거리 문제와 유사하다.

dp를 이용할 것이므로 점화식, 즉 규칙을 찾아내야 한다.

 

첫번째 행은 무조건 자기 자신을 택하므로 제외

 

두번째 행부터는

i) 가장 좌측 원소의 경우 이전 행의 가장 좌측 원소

ii) 가장 우측 원소의 경우 이전 행의 가장 우측 원소를 무조건 택해야 한다.

iii) 위 조건에 해당되지 않는 원소들은 이전 행의 좌측, 우측 원소 중 더 큰 값을 택해야 한다.

 

말로 설명하자니 명확하지 않아 표로 설명해보자면

			1
		5		7
	4		2		5
8		5		4		8

가장 좌측 원소인 5, 4, 8은 무조건 1, 5, 4를 택해야 한다.

가장 우측 원소인 7, 5, 8은 무조건 1, 7, 5를 택해야 한다.

 

위 조건에 해당되지 않는 원소인 2, 5, 4는

(5와 7 중 더 큰 값인 7)

(4와 2 중 더 큰 값인 4)

(2와 5 중 더 큰 값인 5)

를 택하면 되는 것이다. 

 

하지만 주의할 점이 있다. 위 설명은 입력 값인 삼각형에 대해서 계산을 한 것이고 실제로는 누적 합을 이용하여 계산해야 한다.

triangle은 입력 값을 저장한 배열이다.

 

i) dp[i][j] = dp[i-1][j] + triangle[i][j];

ii) dp[i][j] = dp[i-1][j-1] + triangle[i][j];

iii) dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];

 

위 규칙으로 점화식을 유도하고, 이를 통해 누적합을 계산하면 다음과 같다.

			1
		6		8
	10		10		13
18		15		17		21

 

 

해결 과정

점화식을 코드로 구현하고 마지막 행에서 최대값을 찾는 코드를 추가한다.

 

최종 코드는

 

#include <iostream>
using namespace std;

int max(int a, int b){
    return a > b ? a : b;
}

int main(){
    int triangle[500][500];
    int dp[500][500];
    int n, result;
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            cin >> triangle[i][j];
        }
    }
    
    dp[0][0] = triangle[0][0];
    
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if (j == 0){
                dp[i][j] = dp[i-1][j] + triangle[i][j];
            }
            else if (j == i){
                dp[i][j] = dp[i-1][j-1] + triangle[i][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }
    }
    
    result = dp[n-1][0];
    
    for(int i = 0; i < n; i++){
        if (dp[n-1][i] > result){
            result = dp[n-1][i];
        }
    }
    
    cout << result;
}

 

max 함수는 더 큰 값을  return 해주는 함수이다.