[C/C++] 백준 #1932 정수 삼각형(동적 계획법)

이번 문제는 삼각형 형태로 이루어진 숫자 피라미드에서 위의 꼭지점에서 바닥까지 이동을 할 때, 숫자들의 합이 최대가 되는 것을 고르는 것입니다.

 

아랫단에서는 선택할 수 있는 위의 숫자들이 최대 두가지가 됩니다.  이 중 최대값과 더하면 어느 곳이든 꼭지점에서부터 해당 지점까지 오는 경로의 합 중 최대값이 됩니다.  이를 이용해서 프로그램을 작성하면 됩니다.

 

단, 해당 층에서 맨 왼쪽 원소와 맨 오른쪽 원소는 선택할 수 있는 윗단의 숫자가 하이므로 미리 처리를 하든지, 예외 처리를 하시면 됩니다.  제 경우에는 경계처리를 간단하게 하기 위해서 일단 모든 값을 0으로 초기화해서 경계처리를 했습니다.  이렇게 경계처리를 하면 조건 검사를 덜하거나 예외처리를 하지 않아도 된다는 장점이 있습니다.

 

위에서부터 내려오는 방식이 아니고, 아래로부터 위로 가는 방식도 가능합니다.  이 경우에는 모든 숫자들을 다 입력받고서 처리를 해야겠죠.  이 방식이 아무리 생각해도 더 효율적인 방식으로 보입니다.  제가 작성한 것은 두줄의 버퍼를 번갈아 사용해서 메모리 효율을 높이긴 핬지만, 굳이 그렇게 할 필요는 없습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1932
//        - by Aubrey Choi
//        - created at 2019-07-06
//------------------------------------------------
#include <stdio.h>

int main()
{
    int n, s, c, p, max = 0;
    static int v[2][510];
    scanf("%d", &n);
    scanf("%d", &v[1][1]);
    for(int i = 2; i <= n; i++)
    {
        c = i & 1, p = !(i & 1);
        for(int j = 1; j <= i; j++)
        {
            scanf("%d", &s);
            v[c][j] = ((v[p][j - 1] > v[p][j]) ? v[p][j - 1] : v[p][j]) + s;
        }
    }
    c = n & 1;
    for(int i = 1; i <= n; i++)
        if(v[c][i] > max) max = v[c][i];
    printf("%d\n", max);
    return 0;
}

Number Triangle