백준 1932 파이썬 - 정수삼각형 - 동적 계획법

백준 1932 파이썬

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

1932번: 정수 삼각형

가장 상단에서 좌우로만 이동하면서 수의 합이 최대가 되는 경로의 최종 합을 구하는 문제입니다. 해당 문제는 양쪽 끝의 숫자를 제외하고 이전 층에서 인덱스... i-1과 i의 위치를 더한 값을 캐시값으로 저장해서 가장 마지막 층의 최대값을 구하면 된다. 위의 예시에서 메모이제이션을 통해 최종적으로 얻는 캐시값은 아래와 같을 것이다.

 

Python 풀이 1

import sys
read = sys.stdin.readline

n = int(read())
cache = [list(map(int, read().split())) for _ in range(n)]

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

• 층별 값을 미리 리스트에 저장한다.
• 층의 가장 첫번 째 위치는 이전 층의 첫번 째 위치의 값만 더할 수 있다.
• 층의 가장 마지막 숫자도 이전 층의 마지막 위치의 값만 더할 수 있다.
• 나머지 중간에 있는 숫자들은 i와 i-1의 위치값을 더한다.
• 계속해서 합산된 캐시값은 마지막 층으로 내려갔을 때의 최대값들의 나열이다.
• 마지막 층에서 최대값을 출력한다.

문제를 해결하기 위해 저는 매우 1차원적인 방법으로 접근을 했습니다. 하지만 이번 문제는 Python의 내장 함수인 zip의 특성을 이용하면 트리형태로된 가지를 더하는 방법이 있습니다.

 

 

Python 풀이 2

z = zip(
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
)

print(list(z))

zip 함수를 사용해서 크기가 같은 배열을 인자로 넣어주면... 각각 위치에 있는 값을 묶어서 튜플로 반환해준다.

 

• 문제의 예시에서 2번 째 층까지 계산이 되어진 상태이고 3번째 층을 계산하는 과정
• 다음 층을 계산한다고 했을 때... 양쪽 끝은 짝이 안 맞아 0을 추가해서 더한다.

 

계산작업을 해야하는 2번 층에서 양쪽 끝에 0을 추가하면 다음 층의 수를 맞춰줄 수 있다. 이 때 위에서 세로로보고 a+c와 b+c의 조합은 다음 층의 합산 경우의 수가 된다. c는 다음 층의 수이기 때문에 고정되고 a와 b를 변경하는 것이고... 이런 수식을 맞춰주기 위해 양쪽 끝에 0을 더한다.

 

import sys
read = sys.stdin.readline

n = int(read())
cache = []

for i in range(n):
    floor = list(map(int, read().split()))
    cache = [max(a+c, b+c) for a, b, c in zip([0]+cache, cache+[0], floor)]
print(max(cache))

• 내부 함수 zip을 이용해서 위의 표형태를 만들어준다.
  • 현재의 누적된 cache에서 양쪽 끝에 0을 추가하고 현재의 층과 함께 인자로 사용된다.
  • a+c와 b+c 중 최대값을 다시 cache에 넣으면 해당 층에서 구할 수 있는 최대값을 얻는다.
• 최종적으로 마지막 층의 최대값을 얻는다.