[백준 1932] 정수 삼각형

[BanApp]

pypy3

import sys
n = int(sys.stdin.readline())

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

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

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

언제 풀어도 즐거운 DP 문제!
이 문제의 핵심은 연산된 결과 중 더 큰 값을 기존 리스트에 존재하는 값으로 대체해서 누적시키는 것이다.
양 쪽 끝은 올 수 있는 경우의 수가 한 가지씩 밖에 없다.
왼쪽 끝은 바로 한 칸 위 제일 왼쪽, 오른쪽 끝은 바로 한 칸 위 현재 위치부터 한 칸 왼쪽을 더해주면 되고 그 사이에 있는 애들은 두 가지 경우 중에 더 큰애들을 넣어주도록 max 함수를 사용한다.
그렇게 되면 n-1 번째 줄에 더해서 나올 수 있는 모든 경우가 다 담기는데 이것들 중에서 최댓값을 출력해 주면 정답이다!

[ghdcksgml1]

ㅋㅋㅋㅋㅋ dp가 즐겁다니...ㅋㅋㅋㅋㅋㅋㅋ

[BanApp]

실버까지는 즐거움.