11047-동전0

<문제>

https://www.acmicpc.net/problem/11047

11047번: 동전 0

<풀이>

전형적인 그리디 알고리즘 문제이다.

1. k를 가장 큰 화폐의 단위부터 순서대로 나눠준다.

2. k로 나눴을때 몫 = 필요한 화폐의 갯수

3. k로 나눴을때 나머지 = 최소갯수의 화폐로 만들어야 하는 남은 금액

 

-파이썬-

n,k = map(int,input().split())
m_list = []
count = 0
for i in range(n):
    m_value = int(input())
    m_list.append(m_value)
m_list.sort(reverse=True)
for money in m_list:
    count+=k//money
    k%=money
print(count)

-자바-

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken()); //배열의 크기
        int k = Integer.parseInt(st.nextToken()); //목표금액
        ArrayList<Integer> m_list = new ArrayList<Integer>();
        int count = 0;
        for(int i=0;i<n;i++){
            m_list.add(Integer.parseInt(bf.readLine()));

        }
        m_list.sort(Comparator.reverseOrder());
        for(int i=0;i<m_list.size();i++){
            count+=k/m_list.get(i);
            k%=m_list.get(i);
        }
        System.out.println(count);

    }
}