/<> 백준 1932번 : 정수 삼각형 (C언어)

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

 

 

배낭 문제와 원리가 같은 다이나믹 프로그래밍(DP) 문제입니다. 최댓값을 구하는게 그나마 다른 점...?

밑으로 진행할 수록 경우의 수가 하나씩 증가하는데, N번째 줄에서 연산하는 인덱스가 N - 1 을 넘지 않으므로 따로 초기화할 필요 없이 N * N 크기의 배열을 이용하면 됩니다.

 

 

1. 문제에서 입력받는 숫자들을 저장하는 2차원 배열과 합의 경우의 수를 줄마다 저장하는 2차원 배열 dp[][] 를 생성합니다.

 

2. 경우의 수를 저장하는 2차원 배열에 합을 저장할 건데, 이 때 저장하는 방법으로 이전 줄의 왼쪽과 오른쪽 숫자 중 그동안 누적 합이 더 큰 부분을 고른 후 현재 줄의 숫자를 더합니다. 다시 말해 더 큰 숫자를 고르는 것이 아닌, 누적 합이 더 큰 쪽을 고릅니다. dp[][]는 삼각형의 숫자들을 저장하는 것이 아닌, 숫자들의 합을 저장하는 배열이기 때문입니다.

 

3. dp의 마지막 행들의 원소들을 탐색하여, 즉 총합의 경우들을 모두 비교하여 가장 큰 값을 출력합니다. 합하는 경우의 수 모두를 저장해야 하지 않나 느낄 수 있는데, 이미 2번째 단계에서 걸러진 상태라 N가지의 결과들만 비교하면 됩니다.

 

 

<코드>

#include <stdio.h>

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

int main() {
        int n;
        scanf("%d", &n);
        int num[n][n];
        int dp[n][n];
        for(int i = 0; i < n; i++) {
                for(int j = 0; j <= i; j++) {
                        scanf("%d", &num[i][j]);
                }
        }
        dp[0][0] = num[0][0];

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

        int sum = 0;
        for(int i = 0; i < n; i++) if(sum < dp[n - 1][i]) sum = dp[n - 1][i];
        printf("%d\n", sum);
        return 0;
}