문제 출처

단계별로 풀어보기 > 그리디 알고리즘 > 동전 0
https://www.acmicpc.net/problem/11047

문제 설명

동전의 종류 N, 최종 가치의 합 K가 주어질 때,
동전들을 이용하여 k 값이 되는 최소 동전의 개수를 출력하라.

접근 방법

동전의 종류를 내림차순으로 정리한 coin 배열을 이용하여 가장 큰 요소부터 goal이 나눠질 수 있을 때만큼 반복한다. 반복할 때마다 나눈 몫은 sum에 더한다. 이를 coin 배열 전체를 순회한다.

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

public class 동전_0 {
    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 goal = Integer.parseInt(st.nextToken());

        int coin[] = new int[N];

        for(int i = N-1; i>=0; i--){
            coin[i] = Integer.parseInt(br.readLine());
        }

        int sum = 0;

        for(int k : coin){
            while(goal/k !=0){
                sum+=(goal/k);
                goal%=k;
            }
        }

        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
        br.close();
    }
}

Review
단순하게 가치 기준으로 내림차순하여 저장한 배열 coin에 각 배열을 순회하며 K를 나눈 몫을 count에 더한 뒤, K를 나눈 나머지를 순회할 때 다음 값으로 넘겨준다.

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

public class 동전_0_review {
    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 K = Integer.parseInt(st.nextToken());

        int[] coin = new int[N];

        for(int i = N-1; i>=0; i--){
            coin[i] = Integer.parseInt(br.readLine());
        }

        int count = 0;
        for(int i=0; i<N; i++){
            count += K/coin[i];
            K %=coin[i];
        }
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
        br.close();

    }
}

알게된 점

Review
처음 풀이할 땐, 혹시 모를 수를 대비하여 for 안에 while문을 사용하여 몫이 0이 될 때까지 반복했지만, 이는 어차피 한 번 나눌 때 걸러진다.

문제푼 흔적

Review