[백준 / 1932] 정수 삼각형

날짜: 2021년 9월 30일
소요 시간: 1시간 32분 15초
카테고리: 다이나믹 프로그래밍
태그: silver.1, 1932, 파이썬

백준 1932 - 정수 삼각형

입출력 예시

예제 입력	예제 출력
5	30
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

내가 적은 코드

import sys

N = int(sys.stdin.readline())
graph = list()
answer = 0

for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

for i in range(N-2,-1,-1):
    arr = []
    for j in range(len(graph[i])):
        arr.append(max(graph[i][j]+graph[i+1][j], graph[i][j]+graph[i+1][j+1]))
    graph[i] = arr

print(graph[0][0])

풀이 과정

Bottom-up 방식으로 아래부터 위로 올라가면서 계산

가장 아랫층의 바로 윗층부터 가장 윗층까지
선택된 층의 바로 아랫층의 ‘자신과 같은 인덱스’와 ‘+1의 인덱스의 수’를 더한 수 중 더 큰 값을 뽑아 arr에 저장 후
선택된 층의 원소인 배열과 교환

이 과정을 가장 윗층까지 반복하면 마지막 남은 하나의 수는 모든 연산을 했을 때 가장 큰 수가 남게 됨

베스트 코드

def solution():
    import sys
    n = int(input())
    triangle =[]
    for _ in range(n):
        triangle.append(list(map(int, sys.stdin.readline().rstrip().split())))
                   
    accum = []
    for i in range(n):
        accum = [max(a+c, b+c) for a,b,c in zip([0]+accum, accum+[0], triangle[i])]
    print(max(accum))
    
           
    

solution()

반성

베스트코드는 zip()함수를 사용하여 보다 간결하고 빠르게 문제를 풀었다. 파이썬의 다양한 내장함수의 활용도를 높이도록 하자.