[백준] 1932 정수 삼각형 파이썬

푸는 방법

DP(Dynamic Programming)을 이용하여 행이 증가될 때마다, 최고의 값을 구합니다.

 

행을 거듭해가며 더할 때마다 

 

삼각형을 해체해서 경우를 살펴보면 다음과 같습니다.

1. 왼쪽으로만 진행하는 경우

3. 오른쪽으로 증가하는 경우

에는 단순하게 이전행의 마지막값을 더해주면 됩니다.

 

하지만 2번 같이 값이 겹쳐지는 경우에는 각각 더했을 때 최대가 되는 경우를 비교해 선택하면 됩니다.

 

 

코드

 

n = int(input())
tri = []
for _ in range(n):
	tri.append(list(map(int, input().split())))
for i in range(1, n):
	for j in range(i+1):
		if j==0: #왼쪽 행
			tri[i][j] +=tri[i-1][j]
		elif j==i: #오른쪽 행
			tri[i][j] +=tri[i-1][j-1]
        # 값이 겹치는 경우
		else:	tri[i][j] = max(tri[i][j]+tri[i-1][j-1], tri[i][j]+tri[i-1][j])
print(max(tri[n-1]))