1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
> 다이나믹 프로그래밍
7부터 시작하여 아래 그래프로 내려가며 최대가 되는 수를 찾는 문제이다.
위부터 아래로 내려오며 더한 값들이 최대가 되도록 하는 방법을 사용했다. 더한 값들이 최대가 되기 위해선 수에 더할 윗 값들 중 더 큰 수를 더할 수 있을 것이다. 한 행에서 맨 앞에 위치한 수나 맨 마지막에 위치한 수의 경우 위의 줄에서 더할 수 있는 수가 하나밖에 없으므로 다음 그림과 같이 그릴 수 있다.
해당 그림대로 수를 더해보면 다음과 같다.
맨 아래 줄에서 최대값인 30이 7에서 시작해 더할 수 있는 값들 중 최대값이 된다.
위 아이디어를 코드로 구현하면 다음과 같다.
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| [백준 | 파이썬3] 11866. 요세푸스 문제 0 - 큐 (0) | 2021.08.04 |
|---|---|
| [백준 | 파이썬3] 2667. 단지번호 붙이기-dfs활용 (0) | 2021.08.03 |
| [백준 | 파이썬3] 2164. 카드2 - 큐 (0) | 2021.08.02 |
| [백준 | 파이썬3] 10816. 숫자카드 2 - 이진탐색 (1) | 2021.08.01 |
| [백준 | 파이썬3] 2751. 수정렬하기2- 정렬 (0) | 2021.07.31 |