백준_숫자삼각형

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

[ 문제 풀이 법 ]

다이나믹 프로그래밍은 bottom-up방식으로 밑에서 위로 올라가는 방식이다. 분할정복법과 대조된다.

문제풀이법을 살펴보자. 임의의 원소까지의 최대값은 어떻게 될까? 위 예제에서 3행 2열의 값인 1을 임의의 원소로 잡고 여기까지의 최대값은 무엇일까? 최대값을 배열 DP에 저장한다.

아마 대답을 이렇게 미룰 수 있을 것이다. 3행 2열을 오기 바로 전의 최대값 + 3행 2열의 값.

의문은 3행 2열 바로 전까지의 최대값을 바로 알 수 가없다. 그런데, (1, 1)부터 시작하면, 최대값을 하나씩 쌓아갈 수 있다. 그래서 다이나믹 프로그래밍이 bottom-up방식의 문제해결법인 것이다.

3행 2열 바로 전까지의 최대값의 후보는 2행 1열의 값(3)과 2행 2열의 값(8)이다. 이 두 값을 비교해서 큰 값을 선택한다. 나는 코드에서 left와 right라는 변수로 표현했다.

[ Code ]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include<stdio.h> #define MAX 501   int N; int Tri[MAX][MAX], DP[MAX][MAX];   void InData() {     scanf("%d", &N);     for (int i = 1; i <= N; i++)         for (int j = 1; j <= i; j++)             scanf("%d", &Tri[i][j]); }   int main() {     InData();       DP[1][1] = Tri[1][1];     int max = DP[1][1];     for (int i = 1; i <= N; i++)     {         for (int j = 1; j <= i; j++)         {             int left = DP[i - 1][j - 1];             int right = DP[i - 1][j];             if (left > right)                 DP[i][j] = left + Tri[i][j];             else                 DP[i][j] = right + Tri[i][j];               if (DP[i][j] > max)                 max = DP[i][j];         }     }       printf("%d\n", max);     return 0; }