14. 동적 계획법 1
CLASS 4 ESSENTIAL
정수 삼각형의 꼭대기에서 바닥으로 내려올 때 지나온 길의 합의 최대값을 찾는 문제입니다. 정수 삼각형은 N×N의 배열로 받게 되는데, 같은 크기의 배열을 하나 더 만듭니다. 이 배열은 해당 위치까지 지나왔을 때 가질 수 있는 합의 최대값을 저장합니다. 이 값은 해당 위치로 접근한 바로 위 층의 두 위치까지 지나올 때의 합의 최대값 중 큰 값에 해당 위치에 존재하는 정수를 더한 값이 합의 최대값이 됩니다. 이를 맨 위에서부터 채워가서 바닥까지 채운 후, 바닥의 원소 중 가장 큰 값을 출력하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-31 20:24:23 |