[Algorithm] - DP

DP(Dynamic Programming)

---

동적 프로그래밍으로, 큰문제를 작은 문제로 나누어 푸는 문제이다.

• Devide & Conquer과 비슷하지만, DP는 작은 문제로 나누어 반복되는 것을 이용해가면서 푸는 것이다.
• 반복되는 작업을 푸는 것은 Recursion으로 풀이가 가능하지만, 반복되는 작업을 또 하기보다 값을 저장하여 두고 다시 재사용하는 방식으로 푸는 것이 특징. ( Memoization)

 

대표 문제

---

Fibonacci / Knapsack problem

• 아래 그림과 같은 형태로 재귀로 풀이가 가능하지만, 매번 재귀로 풀이시 동일한 값을 또 사용할 수 있다.

Fibonnacci

 

BOJ 2293번

---

• 각 Data에서 단계를 나누어 가능한 경우의 수를 늘려준다.

idx 0   1   2   3   4   5   6   7   8   9   10  (k)
dp  1   0   0   0   0   0   0   0   0   0   0   (초기화)
dp  1   1   1   1   1   1   1   1   1   1   1   (1만 사용하여 k를 만들 수 있는 경우의 수)
dp  1   1   2   2   3   3   4   4   5   5   6   (1과 2를 사용하여 k를 만들 수 있는 경우의 수)
dp  1   1   2   2   3   4   5   6   7   8   10  (1, 2, 5를 모두 사용하여 k를 만들 수 있는 경우의 수)

 

풀이

#BOJ 2293번

n , k = map(int,input().split())
datas = [int(input()) for _ in range(n) ] 
dp = [1] + [0]*(k)
for data in datas :
    for i in range(data,k+1) :
        dp[i] = dp[i-data]+dp[i]

print(dp[k])

 

 

https://www.acmicpc.net/problem/2293

2293번: 동전 1