[백준 1932번] 정수 삼각형 - (python)

문제 링크 : https://www.acmicpc.net/problem/1932

 

Idea

 

 

문제에서 구하라고 하는 것은 모든 층마다 수를 하나씩 선택했을때 그 선택한 수들의 합이 최대가 될때의 그 최대값이다.

그렇다면 각 층마다 가장 큰 값을 선택하면 되지만, 추가 조건으로 특정 층의 특정 위치의 값을 선택하려면 그 이전 층에서 대각선 위치에 있는 값들만 선택할 수 있다. 즉 위 그림에서 꼭대기를 1층이라고 한다면 3층에 있는 1번을 선택하기 위해서는 2층에 3또는 8을 선택해야되고, 3층에 8을 선택하려면 2층에 3을 무조건 선택해야 한다.

 

그림으로 보면 대각선 위치가 한눈에 보이지만 이걸 배열로 저장하면 인덱스 때문에 헷갈릴수 있다.

 

위와같은 형태를 표현하기 위해서는 2차원 배열이 필요하다.

dp라는 2차원 배열을 만들고 dp[x][y] 에는 배열 x,y 에 위치한 값까지 선택했을때의 최대값을 저장해 준다.

가장 마지막 행인 dp[N]에는 마지막으로 각각의 (N,?) 자리 값을 선택했을때의 최대값이 저장되어 있을것이고 거기중 가장 큰 값을 찾아주면 된다.

 

 

풀이

Python

import sys
input = sys.stdin.readline

N = int(input())

tri = []

for _ in range(N):
    tri.append(list(map(int, input().split())))

dp = [[0] * (i + 1) for i in range(N)]
dp[0][0] = tri[0][0]


for x in range(1,N):
    for y in range(len(tri[x])):
        if y-1 >=0:
            dp[x][y] = dp[x-1][y-1]
        if y < len(tri[x-1]):
            dp[x][y] = max(dp[x][y],dp[x-1][y])

        dp[x][y] += tri[x][y]


print(max(dp[N-1]))

 

 

모양이 삼각형이므로 가장 첫번째 행에는 1개 두번째는 2개 이렇게 값이 저장되기 때문에 

 [[0] * (i + 1) for i in range(N)] 으로 식을 만들어서 [[0],[0,0],[0,0,0], .... ] 이렇게 dp 배열을 만들었다.

그 다음 가장 꼭대기 행은 (0,0) 에 있는 자기 자신을 선택하는것이 누적 최대 값이므로 초기 값으로 dp[0][0] 에 tri[0][0] 값을 넣어준다.

 

그리고 나서 점화식을 만들어서 순차적으로 계산을 해서 dp 값을 채워나가면 된다.

이때 현재 구하려는 x 행의 dp값을 구하기 위해서는 이전 행을 살펴봐야 하는데 이때 배열의 인덱스가 범위를 벗어나지 않는지를 체크하면서 값을 구해주면 된다. 

점화식 :  dp[x][y] = max(dp[x-1][y-1], dp[x-1][y] ) + tri[x][y]