[알고스팟/ALGOSPOT] 14. TRIANGLEPATH

안녕하세요~ 알고라파덕입니다~

이번 문제는 동적 계획법 관련 문제입니다.

동적 계획법은 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 방법입니다.

TRIANGLEPATH 문제

 

6

1 2 

3 7 4

9 4 1 7

2 7 5 9 4

위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 삼각형의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에는 각 1개~n개의 숫자로 삼각형 각 가로줄에 있는 숫자가 왼쪽부터 주어집니다. 각 숫자는 1 이상 100000 이하의 자연수입니다.

출력

각 테스트 케이스마다 한 줄에 최대 경로의 숫자 합을 출력합니다.

예제 입력

2
5
6
1  2
3  7  4
9  4  1  7
2  7  5  9  4
5
1 
2 4
8 16 8
32 64 32 64
128 256 128 256 128

예제 출력

28
341

(출처 : https://algospot.com/judge/problem/read/TRIANGLEPATH)

맨 위 6부터 맨 아래줄까지 이동을 하면서 각 칸의 값을 저장합니다.  여러 경우 중에서 

어떤 길로 내려와야 가장 큰 값이 나올지를 구하는 문제입니다.

제가 생각하는 동적 계획법의 방식은 전 단계의 정보를 저장하는 것이라고 생각합니다. 

그래서 항상 어떤 위치에서는 바로 윗줄까지의 모든 경로 중에서 바로 위칸, 바로 위 왼쪽 칸으로 가는 최대값어치를 가져오는 것입니다. 

이런 방식으로 각 단계마다의 누적 최대값을 SUM배열에 저장을 하게 됩니다. 

그 전 단계까지의 최대값을 알 수 있으니 현재의 자신의 자리에 오는 경로를 선택할 수 있습니다.

그리고 마지막 N행에서 최대값을 출력해주시면 문제를 해결하게 됩니다.