다이나믹 프로그래밍 기법
한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법.

탑다운 방식
재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
바텀업 방식
반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식

백준 1932번

✅ 문제

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

위 그림은 크기가 5인 정수 삼각형의 한 모습입니다.
맨 위층 7부터 시작해서맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하세요. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있습니다.

입력 예시

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

출력 예시

30

💻 코드

n = int(input())

data = []

for i in range(n):
    data_list = list(map(int, input().split()))
    for j in range (n, i + 1, -1):
        data_list.append(0)
    data.append(data_list)

for i in range(n):
    for j in range(n):
        # 위에서 오는 경우
        if i == 0:
            up =  0
        else:
            up = data[i-1][j]
        # 왼쪽 위에서 오는 경우
        if i == 0:
            left_up = 0
        else:
            left_up = data[i-1][j-1]
        data[i][j] = data[i][j] + max(up, left_up)

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

설계

삼각형을 n x n 배열에 저장한다. 각 층마다 숫자를 리스트에 저장하고 n개에서 각 층에 있는 숫자를 뺀 만큼을 0으로 채운다.

그림과 같이 바꿔준다.
그러면 현재 층에서 선택된 수는 아래 또는 대각선 오른쪽에 있는 것만 선택할 수 있다. 그래서 위에서 오는 경우와 대각선 왼쪽에서 오는 경우 중 큰 수를 선택하여 최대가 되게 한다.

📝 정리

전에 풀었던 금광 문제와 비슷한 문제였다.