[algo] 다이나믹 프로그래밍

다이나믹 프로그래밍(동적 계획법)이란?

큰 문제를 작은 문제로 나누어 푸는 문제를 일컬음.

제한 사항에 주어지는 숫자 범위가 크고 경우의 수가 엄청난 값의 문제들이 대부분 DP를 이용해서 풀어야 하는 것.

문제 푸는 방법

ex1. 배낭에 넣을 수 있는 물건들의 가치합의 최대값을 구하라면
https://velog.io/@letsbebrave/백준-12865-평범한-배낭

ex2. 연속해서 3번은 안되는 포도주를 가장 최대의 양으로 시식한다면?
https://www.acmicpc.net/problem/2156

Q1. dp 테이블의 행과 열, 기준별 어떤 값을 넣어줄 것인가? (dp 테이블의 구조 생각해주기 - 1차원 배열일 수도 있음)

보통 행이나 인덱스를 지정해줘야 할 때, 현재 물건인 경우가 많음!!

ex1.
dp 테이블 행과 열, 값:
행 - 각 물건
열 - 무게
값 - 각 물건의 무게별 가치합의 최대값

ex2.
dp 테이블 행과 열, 값:
이번엔 1차원 배열로 풀 수 있음
인덱스 - i번째 포도주
값- i번째 포도주까지 "따졌을 때" 마실 수 있는 최대 와인의 양
(i번째 포도주를 무조건 마시는 건 아님)

Q2. 점화식을 세우기 위해 어떻게 케이스를 나눠서 생각해야 하는가?
각 물건별로 무게에 따라 가치합의 최대값이 어떻게 달라져야할지를 생각하며 최대 가치합을 구하기 위한 케이스를 생각해보기

조건에 따라 dp 테이블에 넣어야 하는 값이 달라짐

ex1.

• 현재 물건으로 무게를 만들어 줄 수 없을 때
  (현재 물건의 무게가 열의 무게보다 클 때)
  dp[i][j] = dp[i-1][j]
  내가 들어가지 않았을 때 동일한 무게를 만들어준 최대 가치를 넣어줌
• 현재 물건으로 무게를 만들어 줄 수 있을 때
  두 가지 케이스 존재
  • 현재 물건을 기존의 것에 넣을 때
    현재 물건의 가치(행을 기준으로 for문 돌림) + 나를 넣지 않고 현재 물건의 무게를 뺀 무게일 때 최대값
    value + dp[i-1][j-weight]
  • 현재 물건을 넣지 않을 때
    dp[i-1][j]

두 케이스 중 무엇이 더 큰지 모르므로 max( )를 써서
dp[i][j] = max(value + dp[i-1][j-weight], dp[i-1][j])을 해줘야

import sys
input = sys.stdin.readline

n, k = map(int, input().split()) # n 물품 수 k 최대 무게
stuff = [[0,0]]
for _ in range(n):
    stuff.append(list(map(int, input().split()))) # stuff[0][0] = 무게, stuff[0][1] = 가치
dp = [[0 for _ in range(k+1)] for _ in range(n+1)] # dp 테이블 

for i in range(1, n+1):
    for j in range(1, k+1):
        weight = stuff[i][0] 
        value = stuff[i][1]
        
        if weight > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(value + dp[i-1][j-weight], dp[i-1][j]) # i가 행으로 i-1 아직 내꺼 안 넣었을 때 j는 무게
# print(dp)
print(dp[n][k])

ex2. 각 와인별 i번째까지 고려했을 때 최대 와인의 양을 dp 테이블에 써야 하기 때문에

• i번째 와인을 먹고 + 그 전 꺼 안 먹은 경우
  w[i] + dp[i-2]

• i번째 와인을 먹고 + 그 전 꺼 먹은 경우
  w[i] + w[i-1] + dp[i-3]

• i번째 와인을 안 먹는 경우 🧩 (중요!)
  dp[i-1]

이 세 가지 중 무엇이 최대값인지 모르므로, 점화식은
dp[i] = max(w[i] + dp[i-2], w[i] + w[i-1] + dp[i-3], dp[i-1])

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
w = [0]
for _ in range(n):
    w.append(int(input()))
dp = [0 for _ in range(n+1)]

if n == 1:
    print(w[1])
else:
    dp[1] = w[1]
    dp[2] = w[1] + w[2]
    
    # dp[n]은 n번째 와인까지 따졌을 때 마실 수 있는 최대 와인의 양
    # max() 경우의 수
    # n번째 와인 먹고 + 그 전 꺼 안 먹은 경우: dp[n] = w[n] + dp[n-2]
    # n번째 와인 먹고 + 그 전 꺼 먹은 경우 : dp[n] = w[n] + w[n-1] + dp[n-3]
    # 이렇게만 하면 => 계단 오르기처럼 n번째 와인을 무조건 먹어줘야 ! (즉 마지막 계단을 꼭 밟고 끝나게 됨)
    
    # 그러나 여기선, n번째 와인을 안 먹는 경우를 고려해줘야 : dp[n] = dp[n-1]
    # 점화식
    # dp[n] = max(w[n] + dp[n-2], w[n] + w[n-1] + dp[n-3], dp[n-1])
    
    for i in range(3, n+1):
        dp[i] = max(w[i] + dp[i-2], w[i] + w[i-1] + dp[i-3], dp[i-1])

    print(dp[-1])