거스름돈

 

 

- boj 14916 (www.acmicpc.net/problem/14916)

dp 입문용 문제

i원에서

2원짜리 동전을 선택하는 경우 최소갯수 dp[i - 2] + 1

5원짜리 동전을 선택하는 경우 dp[i - 5] + 1

2 5

 

첫번째 행은 얼마를 만들것인지

두번째 행은 최소 몇개의 동전이 필요한지

(999이상은 MAX로 취급 => MAX 보다 크면 -1 을 출력)

1	2	3	4	5	6	7	8	9	10
999	1	1000	2	1	3	2	4	3	2

 

6원을 만드는 경우

2원을 고르는 경우 => 이전에서 4원을 골랐던 경우 + 1가지 경우(2원 선택) // 2 + 1 = 3

5원을 고르는 경우 => 이전에서 1원을 골랐던 경우 + 1가지 경우(5원 선택) // 999 + 1 = 1000

 

7원을 만드는 경우

2원 => 이전에 5원 // 1 + 1

5원 => 이전에 2원 // 1 + 1

 

8원을 만드는 경우

2원 => 이전에 6원 // 3 + 1

5원 => 이전에 3원 // 1000 + 1

 

9원을 만드는 경우

2원 => 7원 2 + 1 =3

5원 => 4원 2 + 1 = 3

 

10원 만드는 경우

2원 -> 8원 // 4 + 1 = 5

5원 -> 5원 // 1 + 1 = 2

 

- boj