1 분 소요

[공지사항] 알고리즘 카테고리 포스트 살펴보기

:rocket: 문제 설명

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.



:rocket: 문제 풀이

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




public class Main {
    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;
        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

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

        int coinCount = 0;
        for (int i = N-1; i>= 0; i--){
            coinCount += K / coinValue[i];
            K %= coinValue[i];
        }


        bw.write(Integer.toString(coinCount));
        bw.flush();
    }

}

문제 자체는 어렵지 않았다.

코인의 가치가 오름차순으로 입력되고, 첫번째 코인의 가치가 무조건 1이기 때문에 단순히 큰 동전으로 먼저 계산하고 남은 값은 한 단계 더 작은 동전으로 계산하는 과정을 반복하면 된다.

만약 첫번째 코인의 가치가 1이 아니라면 백트래킹 방식을 적용해야 할 것 같다.

첫번째 코인의 가치가 1인 것이 굉장히 중요한 부분인데,

만약 2번째 코인까지 계산하고 남은 값이 홀수일 때, 첫번째 코인의 가치가 짝수라면 계산에 실패하는 경우가 생길 수도 있다.

다행히 여기서는 고정적으로 첫번째 코인의 가치가 1이여서 무조건 해당 코인의 값을 지불할 수 있다.

그렇다면 남은 것은 그리디한 방식으로 접근하여 풀기만 하면 된다.



참고