[BOJ / 파이썬] 1932: 정수 삼각형

백준 / BOJ / Python / 파이썬

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

1932번: 정수 삼각형

단계 : 동적 계획법 1

알고리즘 분류 : 다이나믹 프로그래밍

 

풀이:

삼각형 위에서부터 내려오면서 정수를 더해갔을 때 가장 큰 값을 구하는 문제이다. 단 내려올 때 값은 본인과 맞닿아있는 왼쪽 대각선 아래와 오른쪽 대각선 아래로만 내려갈 수 있다.

 

끝까지 내려왔을 때 가장 큰 값을 구하기 위해 삼각형을 새로 만들 것이다.

삼각형과 똑같은 모양이지만 새로 바뀐 삼각형에는 기존 삼각형의 해당 위치에 있는 값을 더했을 때 최댓값을 저장할 것이다. 

ex) 2의 위치에 1 + 2 해서 3이 들어가고, 3의 위치에 1 + 3 해서 4가 들어간다.

  1       <- 기존 삼각형 / 새로 만든 삼각형 ->       1

2  3                                                                3    4

 

이런 식으로 진행할 경우 새로 만든 삼각형의 맨 아래까지 값이 정해지면 맨 아래 중 가장 큰 값을 구함을 통해 문제의 답을 구할 수 있다.

 

새로 만들 삼각형은 아래의 방식을 통해 만들 수 있다.

1) 삼각형의 값은 누적합이므로 위에서부터 내려오며 정한다.

2) 각 층의 맨 왼쪽과 맨 오른쪽은 각각 윗층의 맨 왼쪽과 맨 오른쪽 값밖에 더하지 못한다.

3) 2에 해당하지 않을 경우는 윗층의 대각선으로 왼쪽, 오른쪽 중 큰 숫자를 더한다.

 

그렇게 삼각형을 새로 만든 후 마지막 변인 ls[n-1] 혹은 ls[-1]의 max 값을 구함을 통해 문제에서 원하는 값을 구할 수 있다.

 

코드

import sys

n = int(sys.stdin.readline())
ls = []

for i in range(n):
    ls.append(list(map(int, sys.stdin.readline().split())))

# 위에서 두번쨰 줄부터 시작해서
# 1)맨 왼쪽은 윗층 맨 왼쪽
# 2)맨 오른쪽은 윗층 맨 오른쪽
# 3)둘 다 해당 안되면  윗층 양 옆 중 큰 숫자 더하기

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

print(max(ls[n - 1]))