[코딩 테스트] DP (동적 계획법)

DP(Dynamic Programming; 동적 계획법)

최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법

추천 문제

LIS (최장 증가 부분 수열)

https://hstory0208.tistory.com/entry/알고리즘-LIS최장-증가-부분-수열이란

추천 문제

• Softeer: https://softeer.ai/practice/6293/history?questionType=ALGORITHM

가방 문제

추천 문제

• https://www.acmicpc.net/problem/12865

해답

• 같은 무게의 다른 가치가 있는 물건도 가방에 담길 수 있으므로 중복 제거하면 안됨

N, K = map(int, input().split())
things = []
for _ in range(N):
  things.append(list(map(int, input().split())))
result = [0] * (K+1)

for k, v in things:
  for w in range(K, k-1, -1):
    result[w] = max(result[w], result[w - k] + v)
print(result[-1])

계단 오르기

추천 문제

• https://www.acmicpc.net/problem/2579

해답

• 계속 오답이 나와서 고생하였다...

import sys
input = sys.stdin.readline

N = int(input())
stair = []
for _ in range(N):
  stair += [int(input())]
dp = [0] * N

if N == 1:
  print(stair[0])
elif N == 2:
  print(sum(stair))
else:
  dp[0] = stair[0]
  dp[1] = stair[0] + stair[1]

  for i in range(2, N):
    dp[i] = max(stair[i] + stair[i-1] + dp[i-3], stair[i] + dp[i-2])

  print(dp[-1])