Pseudo Polynomial - 동전 문제, 막대기 자르기, 합 분해

Pseudo Polynomial

• DP로 전부 다 해보기?

---

동전 문제

• N개의 동전 단위 C[i] 가 있고, 각 동전의 개수는 무한할 때, W원을 동전으로 바꿔주기 위해 필요한 최소 동전의 개수

0원부터 N원까지의 모든 DP 값을 계산하자.
예를 들어 2원, 5원 9원이 있는 상황에 10원을 구하기위한 최소 개수는 아래와 같다.

i	0	1	2	3	4	5	6	7	8
D	1	X	1	X	2	1	3	2	4

아래의 Min은 각각 2원, 5원, 9원을 하나씩 사용했을 때 이다.
점화식 : D[10] = Min(D[8] + 1, D[5] + 1, D[1] + 1)

---

막대기 자르기

• 길이 i인 막대기의 가치 V[i]가 입력으로 주어졌을 때, 길이 N인 막대기를 잘 나누어서 최대 가치로 나누는 문제
• 동전 문제랑 비슷하게 풀면 된다.
• 길이 0 부터 N까지의 모든 DP값을 계산하자.

D[i] = Max(D[i-j] + V[j])
이때, 1≤j≤i

---

합 분해

• 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수
• D[i][j] : i개의 숫자를 사용해서 j를 만드는 경우의 수

D[i][j] = sum(D[i-1][j-k])
이때, 0≤k≤j

⇒ O(N^2K)

i \ j	0	1	2	3	4	5
0	1	0	0	0	0	0
1	1	1	1	1	1	1
2	1	2	3	4	5	6
3	1	3	6	10	15	21
4	1	4	10	20	35	56
5	1	5	15	35	70	126

사실 규칙이 있어서 걍 대각선으로 더해주면 된다.
최적화 D[i][j] = D[i-1][j] + D[i][j-1]

⇒ O(NK)