[백준] 11047 동전0 자바

문제 

https://www.acmicpc.net/problem/11047

 

 

 

동전의 종류와 금액이 주어질때, 해당 동전들을 가지고 금액을 만들기 위한 동전의 최소 개수를 구하는 문제이다. 

동전의 개수가 최소가 되어야하므로 가장 큰 값들로 먼저 계산하면 최솟값을 구할 수 있을것이다. 

 

import java.io.*;
import java.util.StringTokenizer;

public class P32_동전개수의최솟값 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 동전의 종류
        int total = Integer.parseInt(st.nextToken()); // 금액
        int count=0; // 필요한 동전의 개수

        int[] money = new int[n];
        for(int i=0;i<n;i++){
            money[i] = Integer.parseInt(br.readLine());
        }

        // 가장 큰 금액부터 계산하기
        for(int i=money.length-1;i>=0;i--){
            if(total==0) break;
            count += (total / money[i]);
            total%=money[i];
        }
        bw.write(count+" ");

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

🐟 코드 수정할 부분 

큰 값들로 먼저 몫을 구해야 최소의 개수가 나오기 때문에 반복문을 이용해서 큰값 부터 차례대로 나누어서 계산하는 코드를 작성했다. 

위의 코드로 작성하더라도 상관은 없지만,  아래의 코드를 사용한다면 의미 없는 반복이 있을 수 있다는 문제점이 있다. 

 // 가장 큰 금액부터 계산하기
        for(int i=money.length-1;i>=0;i--){
            if(total==0) break;
            count += (total / money[i]);
            total%=money[i];
        }

 

예를들어, 아래와 같은 입력이 주어졌다고 하자.

10 4200 // 동전의 종류 수, 금액
1
5
10
50
100
500
1000
5000
10000
50000

 

위의 for문에 따르면 가장 큰 금액 순서대로 계산이 되기 때문에 50000 → 10000 →   5000 →   1000 →  ..... 순으로 계산이 된다. 

그런데 total= 4200 이기 때문에 4200 보다 큰 50000,10000,5000은 계산 할 필요가 없다. 

 

결국, total값 보다 큰 값으로는 나눌 수 없기 때문에 단순히 반복문을 이용해서 구현한다면 의미 없는 연산이 반복된다. 

 

따라서 " total >= money[i]  "  인 경우에만 연산을 수행하도록 조건을 추가해주면 더욱 효율적인 코드가 될 것 같다. 

 

 

🐙  수정한 코드 

for(int i=money.length-1;i>=0;i--){
    if(total==0) break; // total값이 0이 되면 바로 종료하기
    else if (total>=money[i]) {
        count += (total / money[i]);
        total %=money[i];
    }
}

 

 

🪸 두 코드의 실행시간 비교 

 

 

 

밑에 있는 결과가 첫번째 코드, 위에 있는 결과가 수정 후 코드이다. 역시 수정 후 코드가 조금 더 빠르다.