[백준-11047]-[그리디알고리즘]-동전 0

문제링크 : https://www.acmicpc.net/problem/11047

이문제는 그리디 알고리즘로 풀면 된다. 

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

입력은 위에 처럼 들어오는데 위에는 동전의 수 N, N개의 동전들에서 i개의 최소 조합으로 만들어야 하는 금액 K 이다.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

위의 입력에서 마지막줄에 조건을 볼 수 있다.

N개의 동전의 가치 Ai가 오름차순으로 주어진다는 것과 Ai는 Ai-1의 배수 것이 있다.

동전은 모두 커지고 i번째 동전은 i-1번째 동전의 배수가 된다는 것

이문제는 그리디 알고리즘의 조건을 충족 시키기위한 조건으로 생각하면 될거 같다. 

만약 동전이 1, 4, 5 의 동전이 있고 12의 금액을 맞춰야 한다면 그리디 방식으로 푼다면 5원 동전 2개 1원 동전 2개로 총 4개의 동전을 사용하겠지만

다이나믹 프로그래밍으로 푼다면 4원 동전 3개를 사용함으로 3개를 사용하게 된다. 

이런 예외상황을 막기 위한 것으로 생각하면 될것이다.

다른 문제가 나왔을때 그리디로 플어야 할지 DP로 풀어야 할지는 잘 생각해 보면서 문제를 풀어야 겠다.

괜히 시간 낭비가 될 수 있으니깐..

이문제는 가장 높은 금액부터 차례대로 계산해 나가면서 사용된 개수를 합해가면된다.

목표 금액이 4200 인데 1원 부터 계산해나가면 같은 연산을 반복적으로 해야 할것이다. 

먼저 입력받은 동전중에 단위가 제일 큰 단위는 50000 이다. 

50000으로는 목표 금액인 4200 을 만들 수 있는 조합이 없다.

10000 원, 5000원 도 4200을 만들 조합은 없다.

그 다음 1000원부터 보자.

1000원으로는 4200원 중에 4000을 만들 수가 있다. (4200 / 1000) 하면 정수값으로 1000이 나오고 나머지 값으로 200이 나온다.

1000원으로 만들수 있는 조합 4가 있고

같은 방법으로 가면 100원으로 나머지값 200을 만들수 있는 조합 2가 나온다. 

1000원으로 만드는 조합 4와 100원으로 만드는 조합 2를 더해 6이 답이 된다.

그럼 이과정을 소스로 보자.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B_11047 {
 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int cnt = Integer.parseInt(st.nextToken());
        int value = Integer.parseInt(st.nextToken());
        int[] coins = new int[cnt];
        
        for(int i=0; i < cnt; i++) {
            st = new StringTokenizer(br.readLine());
            coins[i] = Integer.parseInt(st.nextToken());
        }
        int useCnt = 0;
        for(int i=cnt-1; i >= 0; i--) {
            if(value/coins[i] > 0) {
                useCnt += value/coins[i];
                value = value%coins[i];
            }
        }
        System.out.println(useCnt);
    }
 
}