1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
[알고리즘]
DP
[접근 방법]
- 각 층의 양 끝에 있는 수 → 바로 위의 수와 그대로 더해진다
- 중간에 있는 수 → 바로 위의 두 수 중, 더 큰 수와 더해진다
→ 이 방법으로 맨 아래층까지 더하면, n개의 경우의수가 구해지고(n = 층수) , 그 중 가장 큰 수를 출력한다.
[코드]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
n = int(input())
D = []
for _ in range(n):
D.append(list(map(int, input().split())))
for i in range(1, n) :
for j in range(len(D[i])) :
if j == 0 :
D[i][j] = D[i][j] + D[i - 1][j]
elif j == i :
D[i][j] = D[i][j] + D[i - 1][j - 1]
else :
D[i][j] = D[i][j] + max(D[i - 1][j - 1], D[i - 1][j])
print(max(D[n - 1]))
|
cs |
'Algorithm > Dynamic Programming' 카테고리의 다른 글
[Algorithm/Java] 다이나믹 프로그래밍 복습 (0) | 2022.07.14 |
---|---|
[Python] 백준 #11052 카드 구매하기 (0) | 2021.06.30 |
[Python] 백준 #1149 RGB거리 (0) | 2021.06.30 |