2021.12.30 10일차

백준 11047번 (동전 0)

문제

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

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

나의 방법

1. int배열 사용, 입력은 오름차순
2. 큰 값의 경우부터 탐색, for문 뒤에서부터 시작하기
3. 나누었을 때 0이 아닌 경우가 가장 먼저 나온 수가 가장 큰 동전 가치
4. 몫을 개수에 추가
5. 동전 가치와 k의 나머지를 k로 설정
6. k가 0이면 중단

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[] nArr = new int[n];
        for (int i = 0; i < n; i++) {
            nArr[i] = scanner.nextInt();
        }

        int count = 0;

        for (int x = nArr.length - 1; x >= 0; x--) {
            if (k / nArr[x] != 0) {
                count += k / nArr[x];
                k %= nArr[x];
            }
            if (k == 0) {
                break;
            }
        }
        System.out.println(count);
    }
}

생각하기