on1ystar 머릿속을 정리, 기록하는 곳

<백준 1932번-python> 정수 삼각형

16 Feb 2021


풀이 시간 : 20분

시간 제한 : 2초

메모리 제한 : 128 MB

출처 : 백준-1932번 https://www.acmicpc.net/problem/1932


문제

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.


입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.


출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.


내가 적어본 문제 풀이

특별한 방법보단 모든 삼각형 수를 탐색해야 하는데, 아래층으로 내려가면서 수 하나를 선택할 때, 이전에 선택한 수의 영향을 받기 때문에 경우가 매우 많아지므로 다이나믹 프로그래밍 방법으로 문제를 풀어야 한다.

특별하게 원본 리스트(데이터)를 유지해야 된다거나, 안간 곳을 표시해야 하는 게 아니기 때문에 원본 2차원 리스트 tri를 dp 리스트로 사용할 수 있다. 간단하게 점화식(?)을 세워 보면,

tri[i][j] = tri[i][j] + max(tri[i-1][j-1], tri[i-1][j])

여기서 특별히 삼각형을 구현하지 않아도 되므로, 왼쪽 대각선 위는 tri[i-1][j-1] 오른쪽 대각선 위는 tri[i-1][j]로 나타낸다. 현재 위치인 tri[i][j]의 왼쪽 대각선 위와 오른쪽 대각선 위 중, 큰 수를 현재 위치의 수와 더해 저장한다. 그렇게 모든 수를 탐색하고 나면 각 층을 이루는 수들은 자신의 위치에 도달하기 위해 합이 최대가 되는 경로를 선택한 결과가 된다. 따라서 마지막 층의 수들은 각각 최대가 될 수 있는 경로들이 마지막 층의 수와 합한 값들로 이루어 지므로 마지막 층의 수 중 가장 큰 값이 답이다.

n = int(input())
tri = []
for _ in range(n):
    tri.append(list(map(int, input().rstrip().split())))
for layer in range(1,n):
    l = len(tri[layer])
    for i in range(l):
        temp = []
        if (0 <= i-1):  # 왼쪽 대각선 위
            temp.append(tri[layer-1][i-1])
        if (i < l-1):  # 오른쪽 대각선 위
            temp.append(tri[layer-1][i])
        tri[layer][i] += max(temp)
print(max(tri[n-1]))

삼각형을 아래로 내려가면서 한 층씩 탐색하는데, 주의해야 할 점은 IndexError가 발생하지 않도록 따로 검사해줘야 한다. IndexError가 발생할 경우는 2가지로,

  1. i=0에서 왼쪽 대각선 위를 탐색할 경우 try[-1]을 접근하게 됨
  2. i=l-1에서 오른쪽 대각선 위를 탐색할 경우 위 층은 아래 층보다 길이가 1 작기 때문에 인덱스 초과


전체 코드 - https://github.com/on1ystar/algorithm-problem-solving-codes/blob/master/DP/정수 삼각형.py

Related posts