정올 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | import java.util.Scanner; //정올 Q2000 동전 교환 문제 public class Q2000 { //사용가능한 동전 리스트 static int coinList[]; //만들어야 하는 돈 static int target; //결과를 담을 배열 static int result[]; public static void main(String[] args) { //입력부 Scanner sc = new Scanner(System.in); int coinC = sc.nextInt(); coinList = new int[coinC]; for (int i = 0; i < coinC; i++) { coinList[i] = sc.nextInt(); } target = sc.nextInt(); result = new int[target+1]; //함수 function(); //출력 int print = result[target]; if(print ==-1){ System.out.println("impossible"); }else{ System.out.println(result[target]); } } public static void function(){ //i값은 0부터 target까지 순환 for(int i =1;i<=target;i++){ //최소값을 구하기 위해 Max값 저장 int min = Integer.MAX_VALUE; //사용 가능한 동전을 순환 for(int j =0; j<coinList.length;j++){ //조건 //1. 구하려고 하는 i값에서 이용가능한 동전을 뺀값이 0보다 클때 //2. 뺀값이 0보다 크지만 impossible일때(impossible은 -1로 표) if(i-coinList[j]>=0 && result[i-coinList[j]]!=-1){ //가능한 수중 최소값을 구해서 저 if(min>result[i-coinList[j]]){ min = result[i-coinList[j]]; } } } //min값에 변동이 없을시 즉 가능한 값이 없을시 impossible인 -1을 저 if(min==Integer.MAX_VALUE){ result[i] = -1; }else{ //최소값을 저장 result[i] = min+1; } } } } | cs |
▶ 문제 풀이
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가 된다.
