[11047] 동전 0

✔ 동전 0

[백준 11047]

문제 분석하기

그리디 알고리즘으로 풀 수 있도록

뒤의 동전 가격이 앞에 나오는 동전 가격의 배수가 된다는 조건이 부여되어 반례없이 문제를 해결할 수 있도록 하였음

그러므로 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 됨

손으로 풀어보기

1. 가격이 큰 동전부터 내림차순으로 K보다 가격이 작거나 같은 동전이 나올 때까지 탐색
2. 탐색을 멈춘 동전의 가격으로 K를 나눠 몫은 동전 개수에 더하고, 나머지는 K값으로 갱신
3. 위 과정을 나머지가 0이 될 때까지 반복

슈도코드 작성하기

N(동전 개수) K(목표 금액)
A(동전 데이터 배열)
for(N만큼 반복하기)
{
    A 배열 저장하기
}
for(N만큼 반복 → N - 1 ~ 0으로 역순으로 반복하기) {
    if(현재 K보다 동전 가치가 작으면) {
        동전 수 += 목표 금액 / 현재 동전 가치
        목표 금액 = 목표 금액 % 현재 동전 가치
    }
}
누적된 동전 수 출력하기

코드 구현하기

/**
 * 11047) 동전_0
 */
public class D032_11047 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(동전 개수) K(목표 금액)
        int N = sc.nextInt();
        int K = sc.nextInt();
        // A(동전 데이터 배열)
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            // A 배열 저장하기
            A[i] = sc.nextInt();
        }
        int count = 0;
        // 가치가 큰 동전부터 선택
        for (int i = N - 1; i >= 0; i--) {
            // 현재 K보다 동전 가치가 작으면
            if (A[i] <= K) {
                // 동전 수 += 목표 금액 / 현재 동전 가치
                count += (K / A[i]);
                // 목표 금액 = 목표 금액 % 현재 동전 가치
                K = K % A[i];
            }
        }
        // 누적된 동전 수 출력하기
        System.out.println(count);
    }
}