[1932] 정수 삼각형

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

---

동적 계획법으로 해결하는 문제다. 맨 위층 부터 시작해서 대각선 왼쪽과 오른쪽 둘 중 하나를 선택해서 가장 밑으로 내려가는데

가장 밑에까지 갔을 때 최대값을 출력하는 문제이다. 처음에 나는 1차원 배열로 입력받아서 가장 첫번째 수부터 자식 2개중 큰거를 더하면

답이 구해질줄 알았는데, 그렇게 풀면 마지막줄에 엄청 큰값이 있을 때 예외가 생기게 된다. 그러므로 트리 형식으로 풀면 안되는 문제였다.

그래서 내가 문제를 해결한 방식은 2차원 배열 DP[][]를 정하여

제일 위층은 DP[1][1] 이라고 좌표를 설정하고 두번째 줄부터 DP[2][1] DP[2][2], 세번째 줄은 DP[3][1] DP[3][2] DP[3][3] 으로

좌표를 설정하여 각각 의 DP에 최대값을 저장해주는 것이다. 이것이 무슨말이냐면

                              7

                        3           8

                  8          1           0

              2        7           4          4

          4      5           2          6         5

이렇게 주어진 정수 삼각형을 각 단계별 DP로 바꿔보자. 먼저 2번째 줄부터 바꾸게 되면

                              7

                      10          15

                  8          1           0

              2        7           4          4

          4      5           2          6         5

DP[2][1] 은 3+7 이기 때문에 10이되고, DP[2][2]는 8+7 이기 때문에 15가 된다.

                              7

                      10          15

                  18        16          15

              2        7           4          4

          4      5           2          6         5

3번째 줄을 보면 DP[3][1] = 8 은 바로 위의 값인 10과 더하여 18이 되고, DP[3][2]는 10 과 15중 큰값인 15를 선택해서 16이 된다.

DP[3][3]은 바로 위의 값인 15와 더하여 15가 된다.

이러한 식으로 DP[][]를 구성하면 다음과 같은 규칙을 얻을 수 있다.

① 각 줄의 양끝의 좌표는 바로 위의 값과 더하면 된다.

② 양끝의 좌표를 제외한 나머지는 왼쪽 위의 값과 오른쪽 위의 값중 큰것과 더하면 된다.

이러한 식으로 마지막 줄까지 구하고, 마지막 줄에서 가장 큰 값을 선택하게 되면 합이 최대가 되는 경로의 수를 출력할 수 있다.