JArchive 프로그래밍 일기

문제

정수 삼각형 백준 1932번

리뷰

맨 위층부터 아래로 내려가면서 숫자의 합을 구하는데, 최대값을 출력하는 문제다.

선택한 수의 대각선 왼쪽 또는 대각선 오른쪽만 선택할 수 있다는 것이 핵심이다.

입력 배열을 A[n] [n] 으로 두고, 각 위치에서 숫자의 합 최대값을 배열 D[n] [n] 에 저장하는 DP로 풀었다.

삼각형 배열 A 의 인덱스를 표현하면 아래와 같다.

             (1, 1)

           (2, 1) (2, 2)

        (3, 1) (3, 2) (3, 3)

      (4, 1) (4, 2) (4, 3) (4, 4)

(1, 1) 은 1행 1열 을 뜻한다.

예를 들어, A[3] [2] 를 선택한 다음에는 A[4] [2] 또는 A[4] [3] 중에서만 선택 할 수 있다.

그런데 역으로 생각하면, A[4] [2] 는 D[3] [1] 위치에서 더한 최대합에서 오거나, D[3] [2] 위치까지 더한 최대합에서 이동 가능한 위치다.

그래서 D[4] [2] = A[4] [2] + max(D[3] [1] , D[3] [2] ) 가 된다.

왜냐하면 하나를 선택하면, 다음 행에서는 대각선 왼쪽 또는 대각선 오른쪽만 선택할 수 있기 때문이다.

도출된 점화식

D[i][j] = A[i][j] + max(D[i-1][j], D[i-1][j-1]);

모든 행의 1열과 마지막 열에는 위의 점화식으로는 처리하지 못하는 특징이 있다.

1열의 특징

(1, 1) ( 2, 1) (3, 1) 이처럼 1열에 위치한 것의 특징은 아래와 같다.

아래층으로 갈 때 마다 직전 행, 1열의 데이터가 그대로 온다.

예를 들어, (4, 2) 위치는 직전 행의 (3, 1) (3, 2) 둘 중에서 내려올 수 있는 위치다.

(4, 1)위치는 항상 (3, 1) 에서만 선택 당할 수 있다.

따라서 다음과 같은 점화식을 세울 수 있다.

D[i][j] = A[i][j] + D[i-1][j];

마지막열

마지막 열도 비슷하다.

(2, 2) (3, 3) (4, 4) 처럼 행과 열의 인덱스 슷자가 같은 경우를 말한다.

(4, 4)는 오직 (3, 3)에서만 선택 당할 수 있다.

따라서 다음과 같은 점화식을 세울 수 있다.

D[i][j] = A[i][j] + D[i-1][j-1];

A배열의 정수 범위는 (0~9999) 이고, D 배열이 누적합을 저장하기 때문에 D배열의 자료형은 long long 으로 해줘야 한다.

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int A[501][501];
long long D[501][501];

int main(void){

    int n = 0;
    int i, j, num, max_value = 0;

    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        for(j = 1; j <= i; j++){
            scanf("%d", &num);
            A[i][j] = num;    
        }
    } // 입력받기 끝 

    D[1][1] = A[1][1];
    D[2][1] = D[1][1] + A[2][1];
    D[2][2] = D[1][1] + A[2][2];

     for(i = 3; i <= n; i++){

         for(j = 1; j <= i; j++){

              if(j == 1){ // 1열인 경우 
                  D[i][j] = A[i][j] + D[i-1][j];

             }else if(j == i){ // 마지막 열인 경우 
                  D[i][j] = A[i][j] + D[i-1][j-1];

             }else{
                 D[i][j] = A[i][j] + max(D[i-1][j], D[i-1][j-1]);
             }
        }      
    }    

    for(i = 1; i <= n; i++){ // 마지막 줄에서 최대값 찾기 
         if(max_value < D[n][i]){
             max_value = D[n][i];
        }     
    }

     printf("%lld", max_value);

    return 0;
}