22.03.14 - [BOJ] 11047. 동전 0

[suhyunsim]

문제

• 동전

핵심 아이디어

증명: 동전 개수를 최소화 하려면 500원 동전을 최대한 많이 써야 한다?

• 보조 정리 1: 동전을 최소로 소모하면서 물건값을 지불하려면 10/100원 동전은 4개 이하, 50원 동전은 1개 이하로 사용 (by 귀류법: 명제가 거짓이라면 모순이 발생함을 보이는 증명)
  • 거짓이라면?
  • 10/100원 동전을 5개 이상 사용 -> 50/500원 동전으로 대체
  • 50원 동전을 2개 이상 사용 -> 100원 동전으로 대체
• 보조 정리 1 귀류법으로 증명을 할 수 있음
• 500 -> 100 -> 50 -> 10... 순서로
• 배수 관계가 성립해서 가능, 성립하지 않는다면? 같은 풀이가 맞을거라는 보장없음

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q11047;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] cost = new int[n];
        for (int i = 0; i < n; i++) {
            cost[i] = sc.nextInt();
        }
        int answer = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (cost[i] <= k) {
                int cnt = k / cost[i];
                answer += cnt;
                k -= cost[i] * cnt;
            }
        }
        System.out.println(answer);
    }
}