정수 삼각형 - (Dynamic programming - 동적계획법) ★☆☆

이 문제는 정수 삼각형을 이차원 배열에 그대로 넣고, 위에서부터 차례대로 밑의 인접한 값에 자신의 값을 더해주는 것이다.

만약 어떤 수가 위에서 두 방향으로 온다면,

위 발로 그린 그림에서 5에 해당하는 경우 2에서 오는 경우와 3에서 오는 경우가 있는데 둘 중에 큰 값을 넣는다.

현재 8과 9 중에 9를 넣게 된다.

 

이런 식으로 맨 밑까지 값을 구한 후, 마지막 줄에서 가장 큰 값을 찾으면 답이 나오게 된다.