[백준] 1932번 - 정수 삼각형 (DP) - 결과 포함

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

이 문제 또한 전형적인 다이나믹 프로그래밍 문제이다.

어렵게 생각하지 않고 그냥 내가 이 삼각형에서 최대로 합을 구하려면 어떤 방식으로 따라가는 지를 생각했다.

 

아래 층으로 내려가면서 나는 계속 선택할 것이다.

무엇을 더해야 최대가 될까

 

무조건 현재에 최대인 값을 고르는 것이 능사는 아니다.

왜냐하면 선택을 하면 다음 층에서 선택지는 무조건 두 가지로 좁혀지기 때문이다.

만약에 현재 가장 최대인 값을 따라 갔는데 다음 층에서부터 그 길에 작은 값들만 나온다면 합계는 최대가 안 될 가능성이 있다.

 

그러므로 각각의 길을 선택했을 때 어떤 값이 나오는 지를 저장해야 한다.

d라는 리스트를 삼각형과 똑같은 크기로 만들어서 현재까지 이 길을 이용했을 때 합계를 저장하도록 했다.

 

각각의 층의 처음과 마지막 숫자들은 어떤 숫자로부터 온 것인지 알 수 있다. 무조건 각각 윗층의 첫 번째, 마지막 숫자로부터 왔을 것이다.

그러나 가운데에 있는 숫자들은 그 길의 출처를 알지 못한다.

예를 들어

        .......

    8    1    0

2    7    4    4

       ........

삼각형 가운데에 이러한 숫자들이 나왔다.

 

아래층 가운데에 있는 7은 8에서 오는 길과 1에서 오는 길 두 가지의 경우의 수를 갖는다.

그렇다면 두 가지의 경우를 모두 계산해서 더 높은 값을 저장하면 된다.

 

이것을 코딩으로 옮겨본다.

일단 반복문을 돌면서 층을 내려올 것이다.

 

일단 1층은 최상층의 값으로 초기화한다.

 

다음 2층 부터 갈라지는 각각의 길의 합계를 구한다.

각 층 내부에서 또 다른 반복문을 수행하면서 각각의 길의 합계를 구해본다.

 

예를 들어 2층이면 2개의 숫자, 3층이면 3개, ... n 층이면 n 개의 숫자를 탐색한다.

 

일단 합계를 구하는 것은 같은 위치에 있는 숫자끼리 더하면 된다.

 

위의 예시를 보면 2의 위치에 들어갈 합계는 무조건 이전에 8위치에서 구했던 d 리스트의 값에 2를 더한 값이다.

그렇다면 앞에서 이야기 했던 7과 4 같은 가운데에 존재하는 값들을 어떻게 구별할지 고민했다.

 

나는 d가 0이 아닌 경우에는 가운데 값이라고 생각하고 구분했다.

 

예를 들어,

반복문을 따라가보면, 7의 차례가 되었을 때 7과 같은 인덱스 위치에 있는 윗층의 1의 값을 합계로 구해 저장할 것이다.

그러나 8에서 온 값이 더 클 수도 있다. 그러므로 8로부터 오는 길의 합계를 방금 구한 1에서 온 합계와 비교한다.

 

앞에서부터 순차적으로 합계를 구하기 때문에

7과 같은 가운데에 있는 값들은 두 번 합계를 구하고 비교를 진행할 것이다.

 

[소스코드]

n = int(input())

data = []

for i in range(n):
    data.append(list(map(int, input().split())))

d = []
for i in range(1, n + 1):
    d.append([0] * i)

d[0][0] = data[0][0]

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