[Python] 백준 1932 - 정수 삼각형

백준 1932-정수 삼각형

문제

코드

import sys

input = sys.stdin.readline

n= int(input())
t=[]

for i in range(1,n+1):
    t.append(list(map(int, input().split())))

for i in range(1,n):
    for j in range(i+1):
        if j==0:
            t[i][j]=t[i][j]+t[i-1][j]
        elif j==i:
            t[i][j] = t[i][j] + t[i - 1][j-1]
        else:
            t[i][j]=t[i][j]+max(t[i-1][j-1], t[i-1][j])

print(max(t[n-1]))

해설

해당 문제는 다이나믹 프로그래밍을 이용해서 해결했다.

1. 입력: 리스트에 입력값을 append 하여 넣어주었다.
   파이썬을 시작한 지 얼마 안되어서
   엔터를 치면 2차원 배열로 저장이 되는 것을 처음 알았다.

for i in range(1,n+1):
    t.append(list(map(int, input().split())))

2. 다이나믹 프로그래밍 사용
   위에서부터 아래로 내려오면서 값을 더해주어야한다.
   그 중 양 끝 줄, j가 0인 경우와 j가 i인 경우에는 위에서 내려오는 경로가 하나밖에 없으므로 그 값을 더해주면 된다.
   그 외의 경우는 위에서부터 내려오는 경로가 두가지인데 최댓값을 찾는 것이므로 이중에서 큰 값을 더하여주면 된다.

3. 출력: max를 이용해서 큰 값을 출력해준다.