[백준] 11047번 동전 0

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q11047.kt

동전 금액과 목표 금액이 주어진다. 최소한의 동전으로 해당 목표 금액을 만들 수 있을 때, 최소한의 동전
수를 출력하여라.

처음 생각

동전을 최소한으로 사용해야 하므로 큰 동전부터 우선적으로 사용을 해나가면 된다.

▶ 해당 금액으로 몫과 나머지를 따져도 되지만 큰 동전부터 뺄수있는 만큼 빼나가면서 진행을 하였다.

다음 생각

동전수가 세세하게 주어졌기 때문에 그리디 적인 풀이로도 풀이가 가능하다. 만약 동전이 띄엄띄엄 주어졌으면 DFS나 BFS를 통해 풀이를 해야할 것이다.

방안

1) Java 풀이(몫과 나머지 이용)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

import java.util.Scanner;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int m = sc.nextInt(); // 목표 금액         int[] arr = new int[n];         for(int i=0;i<n;i++)             arr[i] = sc.nextInt();           int result = 0;         for(int i=n-1;i>=0;i--){             // 몫이 있다면             if(m/arr[i] >0){                 result += m/arr[i];                 m = m%arr[i];             }         }         System.out.println(result);     } }

2) Kotlin 풀이(반복 뺄셈이용)

▶ Kotlin에서 반복문의 사용이 익숙치 않은것 같다. 획일되어있지 않아서 좀 불편한 느낌이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

package baekjoon.q10000   import java.util.*   fun main(args:Array<String>){     var sc : Scanner = Scanner(System.`in`)     var n = sc.nextInt()     var total = sc.nextInt()     var arr : Array<Int> = Array(n,{0})     for(i in 0..(n-1))         arr[i] = sc.nextInt()     var result = 0     // 최소 동전 수이므로 큰 동전 값부터 살펴보자     for(i in (n-1) downTo 0){         // 큰 동전을 사용할 수 있는 만큼 사용해주기         while(true){             if(total-arr[i]>=0){                 total-=arr[i]                 result++             }else break         }     }     println(result) }