[코딩테스트] 백준 11047 자바

백준 11047

백준 11047 문제

import java.util.Scanner;

public class Boj11047 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 동전의 종류 수
        int k = sc.nextInt(); // 가격
        int[] arr = new int[n]; // 동전의 종류를 담을 배열

        // 배열 초기화
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int count = 0; // 필요한 동전 갯수
        for (int i = n - 1; i >= 0; i--) { // 동전의 가치가 큰 순서대로 계산
            if (k >= arr[i]) { // 동전의 가치가 k보다 작거나 같으면
                count += k / arr[i]; // k를 동전의 가치로 나눈 몫을 count에 더한다.
                k = k % arr[i]; // k의 값을 동전의 가치로 나눈 나머지로 변경한다.
                if (k <= 0) {
                    break; // k가 0보다 작거나 같으면 반복문을 멈춘다.
                }
            }
        }

        System.out.println(count); // 필요한 동전 갯수 출력
    }
}

해당 문제는 그리디 알고리즘으로 풀 수 있도록 뒤의 동전의 가치가 앞의 나오는 동전의 가치의 배수가 된다는 조건을 부여했다. 즉, 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.

풀이

1. 동전의 종류 수를 n으로 받는다.
2. 가격을 k로 받는다.
3. 동전의 종류를 담을 arr 배열을 선언한다.
4. n만큼 반복을 하며 arr 배열을 초기화해준다.
5. 필요한 동전의 갯수 count를 0으로 초기화한다.
6. 동전의 가치가 큰 순서대로 계산하기 위해 배열의 뒤에서부터 반복을 시작한다.
7. 동전의 가치가 k보다 작거나 같으면, k를 동전의 가치로 나눈 몫을 count에 더하고, k의 값을 동전의 가치로 나눈 나머지로 변경한다.
8. k가 0보다 작거나 같아지면 반복문을 break한다.
9. count를 출력한다.