[백준/1932] 정수 삼각형

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

1932번: 정수 삼각형

 간단한 다이나믹 프로그래밍 문제입니다. 전체 소스코드는 다음과 같습니다.

n = int(input())
tmp = []
for _ in range(n):
    tmp.append(list(map(int, input().split())))
    
array = [[0] * (n + 1)]
for item in tmp:
    if len(item) < n:
        item += [0] * (n - len(item))
    array.append([0] + item)
    
table = [[0] * (n + 1) for _ in range(n + 1)]
for c in range(1, n + 1):
    table[1][c] = array[1][c]

for r in range(2, n + 1):
    for c in range(1, n + 1):
        table[r][c] = max(table[r - 1][c], table[r - 1][c - 1]) + array[r][c]

answer = 0
for c in range(1, n + 1):
    answer = max(answer, table[n][c])
print(answer)

 

 삼각형은 항상 정삼각형이며, 한 변의 길이는 1 이상 500 이하입니다. 삼각형의 형태로는 풀이가 힘들기 때문에 정사각형의 형태로 변환시키는 것이 핵심입니다. 저는 각 행마다 n만큼의 길이가 되도록 0을 패딩해주기로 했습니다. 

for item in tmp:
    if len(item) < n:
        item += [0] * (n - len(item))

[[7, 0, 0, 0, 0],
 [3, 8, 0, 0, 0],
 [8, 1, 0, 0, 0],
 [2, 7, 4, 4, 0],
 [4, 5, 2, 6, 5]]

 DP로 문제를 풀기 위한 점화식은 table[r][c] = max(table[r-1][c] , table[r-1][c-1]) + array[r][c]와 같습니다. 즉 위쪽 열에서 같은 컬럼의 값과, 위쪽 열에서 하나 더 작은 컬럼의 값 중 큰 것을 더하는 식입니다. 이 때 하나 더 작은 컬럼에 대한 예외처리가 필요하기 때문에 왼쪽에만 한칸 더 패딩을 해줍니다. (오른쪽으로는 인덱스 에러가 발생하지 않는다는 보장이 있습니다.)

 추가적으로 이렇게 처리하게 되면 컬럼에 대한 접근은 인덱스 1부터 시작하게 되므로, 코드 작성의 용이성을 위해 첫번째 열에도 패딩을 해주는 것이 좋습니다.

array = [[0] * (n + 1)]
for item in tmp:
    if len(item) < n:
        item += [0] * (n - len(item))
    array.append([0] + item)

[[0, 0, 0, 0, 0, 0],
 [0, 7, 0, 0, 0, 0],
 [0, 3, 8, 0, 0, 0],
 [0, 8, 1, 0, 0, 0],
 [0, 2, 7, 4, 4, 0],
 [0, 4, 5, 2, 6, 5]]

 이후에는 DP 테이블을 같은 크기로 만들고, 첫번째 열에 대해서 초기화를 해줍니다.

table = [[0] * (n + 1) for _ in range(n + 1)]
for c in range(1, n + 1):
    table[1][c] = array[1][c]

최종적으로 아까 고안했던 점화식에 대해서 구현하여 DP 테이블을 업데이트하도록 하면 정답을 구해낼 수 있습니다.

for r in range(2, n + 1):
    for c in range(1, n + 1):
        table[r][c] = max(table[r - 1][c], table[r - 1][c - 1]) + array[r][c]

 

정리

 처음 코딩테스트 준비할때는 다이나믹 프로그래밍이 너무 어려웠던 기억이 납니다. 지금은 DP 문제가 제일 쉬운 축에 속한다고 생각할 정도니 아이러니합니다.. 추가적으로 그래프 형태로 테이블을 업데이트해야할 경우, 단순히 반복문의 임시변수를 i, j로 할 것이 아니라 r(row), c(columns)으로 두면 훨씬 직관적이어서 이해하기가 편하네요.