[백준 1932] 정수 삼각형- python (solved.ac - 실버 1)

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

1932번: 정수 삼각형

풀이

문제를 보았을때 알수있는 힌트

리스트에 삼각형의 층별로 담는다. ex) [7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

2번째 층부터 첫번째는 이전 층의 처음을 더하고, 마지막번째는 이전 층의 마지막을 더한다.

첫번째와 마지막번째를 제외한 중간번째들은 이전층의 선택되는 두개의 최대값을 받아서 더한다.

그러면 [[7], [10, 15], [18, 16, 15], [20, 25, 20, 19], [24, 30, 27, 26, 24]] 이렇게 쌓이게 된다.

이후 마지막 층의 최대값이 결과이다.

 

import sys

input = sys.stdin.readline
n = int(input())
list_n=[]
for i in range(n):
    list_n.append(list(map(int,input().split())))

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

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1932.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리