[python] 1932: 정수 삼각형

1932: 정수 삼각형

나의 풀이

DP문제는 누적값을 계산하기에 용이하지 않은가... 하는 생각이 든다.
일단 DP문제를 마주하면 노트에 값을 계산해보고 규칙을 찾는다.

예시

• input

  5
  7
  3 8
  8 1 0
  2 7 4 4
  4 5 2 6 5

• output
  
  표를 그려보면 노란색 화살표로 되어있는 건 그대로 값이 전달되고, 파란색 화살표는 둘중에 max값이 들어간다는 것을 알 수 있다.

코드

import sys
input = sys.stdin.readline

triangleSize = int(input().rstrip())
triangle = [list(map(int, input().rsplit())) for _ in range(triangleSize)]
DP = [[0 for _ in range(triangleSize)] for _ in range(triangleSize)]

maxValue = -1

for h in range(triangleSize):
    for w in range(h+1): # (0,0) (1,1) (2,2)... 까지
        if w == 0: # 맨 왼쪽
            DP[h][w] = DP[h-1][w] + triangle[h][w]
        elif w == h: # 맨 오른쪽
            DP[h][w] = DP[h-1][w-1] + triangle[h][w]
        else:
            DP[h][w] = max(DP[h-1][w-1], DP[h-1][w]) + triangle[h][w]
        if h == triangleSize-1:
            maxValue = max(maxValue, DP[h][w])

print(maxValue)

다른 사람 풀이

DP 리스트를 (1,1)부터 시작하면 triangle 0번째 행과 triangle 0번째 열은 0이 된다. 따라서 w == 0이거나 w == h일 때 max값을 구해도 상관없다.

코드

import sys
input = sys.stdin.readline

triangleSize = int(input().rstrip())
triangle = [list(map(int, input().rsplit())) for _ in range(triangleSize)]
DP = [[0 for _ in range(triangleSize+1)] for _ in range(triangleSize+1)]

maxValue = -1

for h in range(1, triangleSize+1):
    for w in range(1, h+1):
        DP[h][w] = max(DP[h-1][w-1], DP[h-1][w]) + triangle[h-1][w-1]
        if h == triangleSize:
            maxValue = max(maxValue, DP[h][w])

print(maxValue)

참고 자료

바킹독