문제

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

30

나의 코드

from sys import stdin as s

s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n = int(s.readline().strip())

triangle = []

for i in range(n):
    triangle.append(list(map(int, s.readline().strip().split())))

for i in range(1, n):
    for j in range(i + 1):
     # 왼쪽 위가 없을 경우
        if j == 0:
            triangle[i][j] += triangle[i - 1][j]
     # 오른쪽 위가 없을 경우
        elif j == i:
            triangle[i][j] += triangle[i - 1][j - 1]
     # 위에 왼쪽, 오른쪽 둘다 있을 경우
        else: 
            triangle[i][j] += max(triangle[i-1][j-1], triangle[i - 1][j])

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

요즘은 2차원 DP에 재미가 들렸다. ㅋㅋㅋㅋ
2차원 DP를 몰랐을 때 저 문제를 처음 봤을 때는 도저히 풀이 방법이 떠오르지 않았는데, 2차원 DP를 알게되니 문제가 아주 간단해졌다.
왼쪽 위의 숫자와 오른쪽 위의 숫자 중 더 큰 숫자와 현재 나의 숫자를 더한 값으로 현재 나의 값을 변경하면 되는 문제이다.

그런데 아직도

IndexError: list index out of range

를 자주 만난다.

처음에

     # 오른쪽 위가 없을 경우
        elif j == i:
            triangle[i][j] += triangle[i - 1][j - 1]

이 부분을 생각 못해서 틀렸었다.

각 행에서 마지막 인덱스의 경우 triangle[i-1][j]가 없기 때문이다.

반성

첫번째 인덱스는 왼쪽 위를 참조하면 out of range인 게 생각이 났으면,
오른쪽도 자동반사적으로 오른쪽 위를 참조할 수 있는지 확인해야 하는 것 아니야??!!

생각해보면 코드를 작성하기 전에 떠오르긴 했는데 막상 코드를 짤 때는 잊어버렸던 것 같다. ㅋㅋㅋ

여튼 자그마한 실수지만 앞으로도 같은 실수 안하려면 짚고 넘어가길 잘한 것 같다.

결론

2차원 DP 꿀잼!