[백준/C언어] 1932번 - 정수 삼각형

백준 웹사이트 "1932번 - 정수 삼각형" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1932번: 정수 삼각형

---

소스 코드

#include <stdio.h>

int max(int a, int b);

int main(void){
    int n;
    scanf("%d", &n);

    int triangle[n][n]; //정수 삼각형: triangle[i][j] ->  triangle[i+1][j] or triangle[i+1][j+1]
    for(int i=0; i<n; i++){
        for(int j=0; j<=i; j++){
            scanf("%d", &triangle[i][j]);
        }
    }

    int path[n][n]; //경로의 최대 합: path[i][j]는 i번째 줄 j번째 숫자까지의 최대 합 경로
    path[0][0] = triangle[0][0];
    for(int i=1; i<n; i++){
        for(int j=0; j<=i; j++){
            if(j==0)   //줄의 첫 숫자일 경우
                path[i][j] = path[i-1][j] + triangle[i][j];
            else if(j==i)  //줄의 마지막 숫자일 경우
                path[i][j] = path[i-1][j-1] + triangle[i][j];
            else
                path[i][j] = max(path[i-1][j-1], path[i-1][j]) + triangle[i][j];
        }
    }
    
    //마지막 줄 최대 경로의 합
    int max=0;
    for(int i=0; i<n; i++){
        //printf("%d ", path[n-1][i]);
        if(path[n-1][i]>max)
            max = path[n-1][i];
    }
    //printf("\n");
    printf("%d\n", max);
}

int max(int a, int b){
    if(a>b)
        return a;
    else
        return b;
}

---

문제 풀이

  가장 먼저 정수 삼각형을 저장할 배열 'triangle[n][n]'을 선언하고 입력받습니다. 이때 triangle[i][j] 바로 아래에 있는 두 수는 triangle[i+1][j]와 triangle[i+1][j+1]이 되도록 하여, 경로를 구할 때 둘 중 하나가 선택되도록 합니다.

  배열 'path[n][n]'은 각 수까지 합이 최대가 되는 경로에 있는 수의 합입니다. 즉, path[i][j]는 i번째 줄 j번째 숫자까지의 최대 합 경로입니다. 'path[0][0] = triangle[0][0]'으로 초기값을 정해준 뒤, 동적 계획법으로 전체 배열을 채웁니다. 동적 계획법을 시행한 소스 코드 Line 18 ~ 27의 코드는 아래와 같습니다.

 

for(int i=1; i<n; i++){
        for(int j=0; j<=i; j++){
            if(j==0)   //줄의 첫 숫자일 경우
                path[i][j] = path[i-1][j] + triangle[i][j];
            else if(j==i)  //줄의 마지막 숫자일 경우
                path[i][j] = path[i-1][j-1] + triangle[i][j];
            else
                path[i][j] = max(path[i-1][j-1], path[i-1][j]) + triangle[i][j];
        }
    }

 

  줄의 첫 숫자이거나 마지막 숫자일 경우, 바로 위의 숫자는 유일하므로 경로 역시 한 가지입니다. 바로 위 숫자의 path값과 현재 숫자의 값을 더하면 됩니다.

  줄의 첫 숫자/마지막 숫자가 아닐 경우, 다음과 같은 점화식으로 최대 합 경로를 구할 수 있습니다.

$$ path[i][j] = max([path[i-1][j-1], path[i-1][j]) + triangle[i][j] $$

(i, j) 위치의 숫자는 반드시 (i-1, j-1) 또는 (i-1, j) 위치와 연결되므로 두 경로 중 큰 최대 합 경로를 선택합니다. 이러한 과정을 반복하면 최종 최대 합 경로는 마지막 n개 숫자들의 path값 중 하나입니다.

  마지막으로 overflow가 일어나지 않는지 검사하는 것이 좋은데, 문제의 조건에 따라 얻어지는 최대 합의 최댓값은 500 × 9999입니다. 이는 int범위를 넘지 않기 때문에 overflow가 일어나지 않음을 확인할 수 있습니다.