[Baekjoon] 11047 - 동전 0

📝 문제

 

 

🔑 풀이 과정

바로 앞에서 풀었던 2839번 문제(설탕 배달)과 비슷한 문제.

 

동전을 배열로 입력받는다.

(문제 조건을 보면  i ≥ 2인 경우에 Ai는 Ai-1의 배수라고 적혀있음, 즉 오름차순으로 입력받게 된다.)

 

동전의 최솟값을 구하는 것이므로 값이 제일 큰 동전부터 입력받은 금액과 비교한다.

① 현재 가리키는 동전이 금액보다 크면 

그 동전을 쓸 수 없다는 뜻으로, 그것보다 작은 동전으로 넘어간다.

② 현재 가리키는 동전이 금액보다 작거나 같으면

그 동전을 쓸 수 있다는 뜻으로, (금액/동전)값 만큼 count를 증가해준뒤, 금액을 (금액%동전)으로 변경해준다.

이를 인덱스 0까지 계속 반복한다.

 

참고로 이 문제 조건에서 금액은 무조건 1이상이고, 동전개수도 1이상, 첫번째 동전은 무조건 1원이므로

해가 없는 경우는 없다(고려하지 않는다).

 

 

 

 

🔓 답안

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

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 = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] c = new int[N];

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

        int count = 0;
        for(int i = N-1; i >= 0; i--){
            if(c[i] > K){
               continue;
            } else{
                count += (K / c[i]);
                K = K % c[i];
            }

	    //이 부분은 없어도 문제풀이에 영향은 없으나, 불필요한 반복을 줄여준다.
            if(K == 0)
                break;
        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 그리디 알고리즘