✏️ 문제

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

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

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

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

예제 입력

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

예제 출력

30

첫번째 풀이

📝 문제풀이 - 이차원 배열 사용

동적 프로그래밍을 이용하는 문제로 배열을 생성한 후 점화식을 구해 문제를 생성해야겠다고 생각했다.
입력한 배열 값을 이차원 배열로 생성하고, 메모이제이션 d도 이차원 배열로 생성했다.

         7
      10   16
    18   17   16
-> 17은 10과 16을 비교하여 더 높은 값인 16과 원래 있던 1을 더한 값이다.
  20   25   21   20
-> 25는 18과 17을 비교하여 더 높은 값인 18과 원래 있던 7을 더한 값이다.
24   30   27   27   25

1. 삼각형의 꼭대기부터 차례대로 더 큰 수를 비교하여 덧셈한 것을 모두 메모이제이션에 저장한 후
2. 삼각형의 가장 마지막 줄에서 큰 값을 출력한다.

점화식은 다음과 같다.

d[i][j] = max(d[i-1][j-1], d[i-1][j]) + tri[i][j]
이때, i는 삼각형에서 행을 의미하고 j는 열을 의미한다.

👩🏻‍💻 소스코드 - 이차원 배열 사용

import sys

n = int(sys.stdin.readline().rstrip())
tri = []
for i in range(n):
    tri.append(list(map(int, sys.stdin.readline().split())))

d = [ [0] * n for _ in range(n) ]

d[0][0] = tri[0][0]
d[1][0] = tri[1][0] + tri[0][0]
d[1][1] = tri[1][1] + tri[0][0]

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

print(max(max(d)))

두번째 풀이

📝 문제풀이 - 일차원 배열 사용

메모이제이션을 이차원 배열을 사용하여 문제를 풀고 나니 이차원 배열의 마지막 줄만 필요하기 때문에 굳이 이차원 배열을 사용할 필요가 없다고 생각했다.

         7
      10   16
    18   17   16
  20   25   21   20
24   30   27   27   25

최댓값을 구하기 위해서는 모두 합한 값인 마지막 줄만 필요하기 때문에 메모이제이션에는 최종적으로 마지막 줄만 남아있으면 된다.
점화식은 이차원 배열 사용했을 때와 동일하다.

👩🏻‍💻 소스코드 - 일차원 배열 사용

import sys

n = int(sys.stdin.readline().rstrip())
tri = []
for i in range(n):
    tri.append(list(map(int, sys.stdin.readline().split())))

d = [0] * n

d[0] = tri[1][0] + tri[0][0]
d[1] = tri[1][1] + tri[0][0]

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

print(max(d))

함수를 이용해서 시간을 더 줄여볼 계획이 있다!