정올 Q2000 동전 교환
▶ 문제 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1273&sca=3050
우리나라 동전의 단위는 1원, 5원, 10원, 50원, 100원, 500원의 6단계로 이루어진다. 잔돈 256원을 내주려면 500원 0개, 100원 2개, 50원 1개, 5원 1개, 1원 1개로 해서 모두 5개의 동전이 필요하다.
만약 동전 단위가 1원, 4원, 6원의 3단계로 이루어진 나라에서 8원을 내주려면 6원 1개, 1원 2개도 가능하고, 4원 2개로 가능하다. 앞의 경우에는 동전 3개, 뒤의 경우에는 동전이 2개 필요하다.
동전의 개수를 최소로 하면서 동전을 내주는 것이 목적이라면 뒤의 방법을 택해야 한다.
동전의 단위들이 주어지고, 원하는 잔돈이 주어질 때, 그 잔돈에 맞추기 위해 필요한 최소의 동전 수를 구하시오. 갖고 있는 동전의 수는 무한하다.
▶ 문제 접근
일반적인 형태의 다이나믹 문제로 쉬운 편에 속한다.
문제를 보면 점화 식 보다는 분할 정복 문제에 가깝다는 것을 알 수 있다.
다이나믹 문제에서 중요한 접근 방식은 N을 정하는 것이라 생각된다. 대부분의 경우 N은 기준이 되는 값이다. 이 문제의 N은 가격으로 설정하고 접근하였다. 즉 위 예제는 f(8)을 구하는 방법으로 문제에 접근하였다.
▶ 문제 풀이
1. N은 목표로 하는 가격이다. 코드 상에서 target 변수로 설정한다.
2. 분할 정복방식으로 f(1)부터 구해나간다.
3. 위 예제에서 사용 가능한 동전은 1, 4, 6이다.
f(1) = 1이 된다.
f(2)를 구하는 방법은 2번째 for문을 보자
coinList를 순환하면서 2-coin을 수행해본다.
1인 경우 2-1로 0보다 크고 f(1)의 값이 -1아니므로 if문에 적합하다.
(-1은 생성이 불가능한 숫자를 뜻한다 출력부분에서 -1인 경우 impossible을 출력하게 했다.)
따라서 f(1)값에 1개를 더 쌓은 갯수가 된다.
하지만 4, 6인경우 조건에 만족하지 않으므로 if문에 들어오지 않는다.
f(2) = 2;
f(3) = 3;
f(4) = 1;
f(5) = 2;
f(6) = 1;
f(7) = 2;
이렇게 단계별로 답이 나올 것이다.
f(8)의 경우
8-1=7, 8-4=4, 8-6=2가 된다
따라서 f(7), f(4), f(2)중 가장 작은 값에 1을 더 한 값이 f(8)이 된다.
f(8)은 2가 된다.
'알고리즘 > 다이나믹' 카테고리의 다른 글
| 정올 Q1871 줄세우기 (2) | 2016.09.02 |
|---|---|
| 정올 Q1407 숫자카드 (0) | 2016.08.30 |
| 정올 Q1539 가장 높은 탑 쌓기 (0) | 2016.08.26 |
| 정올 Q1848 극장좌석 (0) | 2016.08.26 |
| 정올 Q1491 자동차 경주 대회 (0) | 2016.08.19 |
