[백준] 11047번: 동전 0 - JAVA

🔗 문제 링크

BOJ 11047번: 동전 0

11047번: 동전 0

 

📝 풀이 과정

$A_i$가 $A_{i-1}$의 배수이기 때문에 그리디로 문제를 해결할 수 있다.

 

동전의 가치가 큰 순서대로 K값을 넘지 않는 최대 개수만큼 값을 빼주면서 K = 0일 때까지 계산하면 되는 문제이다.

동전(A)이 오름차순으로 입력이 주어지기 때문에, 반복문을 i = n - 1로 시작해 역순으로 진행하면 된다. 종료 조건은 2가지를 걸어주었는데 K > 0이어야 아직 계산이 종료되지 않은 경우이다.

 

cnt변수에 i번째 동전으로 계산할 수 있는 최대 몫을 넣어주고, K는 그만큼 빼주어야 하기 때문에 %연산을 통해 나머지를 대입해준다.

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), K = sc.nextInt();

        int[] A = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = sc.nextInt();

        int cnt = 0;
        for (int i = N - 1; i >= 0 && K > 0; i--) {
            cnt += K / A[i];
            K = K % A[i];
        }
        System.out.println(cnt);
    }
}

 

📊 제출 결과