[알고리즘] 1183. 동전 자판기 (하)

0. 문제

 

JUNGOL

 

---

1. 문제 이해

 

1. 그리디 - 동전자판기 변형

 

---

2. 제출

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class JOL1183 {
    static int W, allMoney, useCnt;
    static int[] cnt, ret;
    static final int[] coins = { 500, 100, 50, 10, 5, 1};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        allMoney = 0; useCnt=0;
        cnt = new int[6];
        ret = new int[6];

        W = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<6; i++) {
            cnt[i] = Integer.parseInt(st.nextToken());
            allMoney += cnt[i] * coins[i]; // 가지고 있는 돈의 총액을 구한다.
        }

        solve();

        StringBuffer sb = new StringBuffer();
        //사용된 동전의 수
        sb.append(useCnt).append("\n");
        for(int i : ret) {
            sb.append(i).append(" ");
        }
        System.out.println(sb);
        br.close();
    }

    static void solve() {
        int notUseCnt;
        int other = allMoney - W; // 사용하지 않을 돈
        // 사용할 동전의 수가 최대다. = 사용하지 않는 동전이 최소가 된다.
        for(int i=0; i<6; i++){
            notUseCnt = other/coins[i];
            if(notUseCnt > cnt[i]) notUseCnt = cnt[i]; // 가지고 있는 동전의 수를 넘어설 순 없다.
            ret[i] = cnt[i] - notUseCnt; // 사용한 동전 = 가지고 있는 동전 - 사용하지 않을 동전
            useCnt += ret[i];
            other -= coins[i]*notUseCnt;
        }
    }
}

• “사용할 동전의 수를 최대로”는 “사용하지 않는 동전을 최소로”와 동일하다.
• allMoney += cnt[i] * coins[i]; : 가지고 있는 돈의 총액을 구한다.
• ret[i] = cnt[i] - notUseCnt; : 사용한 동전 = 가지고 있는 동전 - 사용하지 않을 동전

 

---