[백준알고리즘/1932번/파이썬] 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

문제: 정수 삼각형이 주어졌을 때, 맨 위층부터 맨 아래층 까지 도달할 수 있는 경로 중 경로에 있는 값의 합이 최대가 되는 값을 구하는 문제입니다.

 

풀이 방법: 다이나믹 프로그래밍

 

풀이 코드:

import sys
input = sys.stdin.readline

n = int(input())

triangle = []

for _ in range(n):
    triangle.append(list(map(int,input().rstrip().split())))
if n == 1:
    print(triangle[0][0])
    sys.exit(0)

for i in range(2):
    triangle[1][i] += triangle[0][0]


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

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

풀이 설명:

 

풀이 코드에서 핵심 코드인 다음 코드를 설명하고 넘어가겠습니다.

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

각 줄의 양 끝 값은 이 전줄의 하나의 값이랑만 연결이 되기 때문에,

 

j == 0 일 경우, triangle[i - 1][j] 가 더해지게 했고

j == len(triangle[i]) - 1 일 경우, triangle[i - 1][j - 1]이 더해지게 하였습니다. 이때 인덱스가 (i - 1, j - 1)인 이유는 이전 줄은 현재 줄보다 길이가 1 작기 때문입니다.

 

마지막으로, 양 끝 값이 아닌 경우에는 이 전줄의 2개의 값과 연결이 되기 때문에

이어지는 두개의 값중 큰 값을 더하도록 하였습니다.

 

이 코드를 한줄로 표현하면 다음과 같이 나옵니다.

triangle[i-1][j] if j == 0 else triangle[i-1][j-1] if j ==(len(triangle[i])-1) else max(triangle[i-1][j-1],triangle[i-1][j])

 이 코드를 풀어 쓴다면 다음과 같이 나옵니다.

if j == 0 :
    triangle[i][j] += triangle[i - 1][j]
    
elif j ==(len(triangle[i])-1):
    triangle[i][j] += triangle[i-1][j-1]

elif 0 < j < (len(triangle[i])-1):
    triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j])