[BOJ-1932][C++] 정수 삼각형

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

입력

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

 

출력

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

 

예제 입력 1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 

예제 출력 1

30

 

출처

Olympiad > International Olympiad in Informatics > IOI 1994 > Day 1 1번

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 출처

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

---

 

문제 해결 방법

• RGB거리 문제(BOJ-1149)와 비슷한 방식으로 문제를 풀었다.
• 이 문제는 N 개의 줄을 갖는 2차원 배열에서 각 줄에서 가중치 하나를 선택해서 가중치 합의 최댓값을 출력하는 문제이다. (단, N+1번째 줄에서 숫자를 선택할 경우, N번째 줄에서 선택한 수의 왼쪽 대각선 아래쪽 또는 오른쪽 대각선 아래쪽에 있는 수를 선택해야 한다.)
• 예제를 이용하여 그림을 그리면 쉽게 풀 수 있는 문제였다.

 

 예제를 이용하여 문제 이해하기

• 예제 입력 1의 테스트 케이스를 이용하여 문제가 해결되어지는 과정을 그림으로 표현하면 다음과 같다.

• 위에서 아래로 내려가면서(왼쪽 대각선 아래쪽 또는 오른쪽 대각선 아래쪽) 가중치들을 더해 나간다.
• 그리고 가중치의 합이 최대일 경우, 그 때의 가중치의 합(7 + 3 + 8 + 7 + 5 = 30)을 출력한다.
• 이 문제를 DP를 이용하여 해결하려면 밑으로 내려 가면서 DP 테이블을 업데이트 해나가야 한다.
• 아랫줄에 있는 각 가중치들을 업데이트하려면, 아랫줄의 각 가중치와 윗 줄에 있는 두 요소(왼쪽 대각선 위쪽(dp[i - 1][j - 1]) 또는 오른쪽 대각선 위쪽(dp[i - 1][j])) 중 최댓값(max)을 더해줘야 한다.
  • dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j]);
    • 삼각형 모양의 요소들을 2차원 배열에 첫번째 인덱스부터 하나하나씩 넣기 때문에 인덱스 위치를 잘 파악해야 한다. 
  • 단, 각 줄에서 첫 번째 위치(j == 0)또는 마지막 위치(j == i)에 있는 가중치의 경우, 오른쪽 대각선 위쪽 또는 왼쪽 대각선 위쪽에만 가중치가 존재한다. 
  • 따라서 이 경우에는 각각의 조건에 맞게 가중치를 업데이트 해준다. (2차원 배열을 이용하여 문제를 풀었기 때문에, 배열의 인덱스 범위를 넘어가는 일이 발생하지 않도록 하는 것이 중요했다.)
    • 첫 번째 위치(j == 0)에 있는 가중치 : dp[i][j] += dp[i - 1][0];
    • 두 번째 위치(j == i)에 있는 가중치 : dp[i][j] += dp[i - 1][j - 1];
• 이러한 과정을 마지막 줄까지 반복하면, 다음과 같이 DP 테이블에 업데이트 된 가중치의 합들이 들어가게 된다.

• 마지막 줄(i = 5)에는 가중치들의 합의 모든 경우가 들어가 있게 되고, 이 중에서 최댓값이 가중치들의 합의 최댓값이 된다.

 

코드 작성하기

• 위의 내용을 코드로 표현하면 다음과 같다.

			
			
			
		
int Calc(int n) {
    int result;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] += dp[i - 1][0];
            }
            else if (j == i) {
                dp[i][j] += dp[i - 1][j - 1];
            }
            else {
                dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
    }
 
    // 최댓값 구하기
    result = -1;
    for (int i = 0; i < n; i++) {
        if (result < dp[n][i]) {
            result = dp[n][i];
        }
    }
 
    return result;
}

 

코드

			
			
			
		
#include <iostream>
#include <cmath>
using namespace std;
 
int n;
int dp[501][501];
 
void Input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> dp[i][j];
        }
    }
}
 
int Calc(int n) {
    int result;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] += dp[i - 1][0];
            }
            else if (j == i) {
                dp[i][j] += dp[i - 1][j - 1];
            }
            else {
                dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
    }
 
    // 최댓값 구하기
    result = -1;
    for (int i = 0; i < n; i++) {
        if (result < dp[n][i]) {
            result = dp[n][i];
        }
    }
 
    return result;
}
 
void Output() {
    cout << Calc(n) << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    Input();
    Output();
 
    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [동적 계획법 1]
• 실버I