코딩테스트 대비/BOJ
[Baekjoon/Python] 1932번: 정수 삼각형 - 효과는 굉장했다!
bluetag_boy
2022. 4. 3. 18:17
반응형
1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
알고리즘 분류
- 다이나믹 프로그래밍
SOLUTION
import sys
n = int(sys.stdin.readline())
triangle = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
for i in range(1,n):
for j in range(len(triangle[i])):
if j == 0: # 제일 왼쪽 숫자
triangle[i][j] += triangle[i-1][j]
elif j == i: # 제일 오른쪽 숫자
triangle[i][j] += triangle[i-1][j-1]
else: # 왼쪽 대각선, 오른쪽 대각선 양쪽에서 올 수 있는 경우는 그 둘 중 큰 값을 넣는다
triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
print(max(triangle[n-1])) # 마지막 가지에서 최댓값 출력