동전 0(11047번)

• 티어 : Sliver 4
• 정답여부 : 정답
• 알고리즘 유형 : 그리디 알고리즘
• 시간 제한 : 1초

💡문제

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

동전을 적절히 사용해서 그 가치의 합을 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의 배수)

💡출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

💡예제 입력 1

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

💡예제 출력 1

6

💡예제 입력 2

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

💡예제 출력 2

12

💡문제요약

• 가지고 있는 동전들 중 K만큼 동전을 채우는데 그 K만큼 만들수 있는동전의 최적의 수를 구하면 되는 문제

💡알고리즘 설계

• N : 가지고 있는 동전의 개수
• K: 동전의 값
• cnt : 최적의 수

1. 가지고 있는 동전들을 N만큼 입력받는다.
2. 동전을 내림차순을 시킨다.
3. 가지고 있는 동전들을 보는데 가지고 있는 동전이 동전의 값과 같거나 작을 경우 그 동전을 나눠주고 몫은 cnt에 나머지는 K에 넣어줌으로 최적의 수를 구하면 되는 문제

💡작성코드

• Java

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 동전의 개수
		int K = Integer.parseInt(st.nextToken()); // 동전의 값;
		Integer coin[] = new Integer[N]; // 동전들 갯수들
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(coin, Comparator.reverseOrder()); // 내림차순
		for(int i = 0; i < N; i++) {
			if(coin[i] <= K) {
				cnt += K / coin[i];
				K %= coin[i];
			}
		}
		System.out.println(cnt);
	}
}

💡시간복잡도

O(NlogN)

💡틀린 이유 or 수정할 부분

한번에 통과

사실 내림차순을 하지 않아도 값을 구할 수 있는 풀이를 가져왔다.

💡틀린 부분 수정 or 다른풀이

• Java

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 동전의 개수
        int K = Integer.parseInt(st.nextToken()); // 목표 금액
        int[] coin = new int[N]; // 동전들의 가치
        int cnt = 0; // 필요한 최소 동전의 개수
        for(int i = 0; i < N; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
        // 내림차순 정렬 없이 큰 동전부터 검사
        for(int i = N - 1; i >= 0; i--) {
            if(coin[i] <= K) {
                cnt += K / coin[i]; // i번째 동전으로 K를 나눈 몫을 cnt에 더함
                K %= coin[i]; // K를 i번째 동전으로 나눈 나머지로 갱신
            }
            if(K == 0) break; // K가 0이 되면 반복문 종료
        }
        System.out.println(cnt); // 필요한 동전의 최소 개수 출력
    }
}

💡느낀점 or 기억할 정보

뭐든 문제를 잘 이해하면 알고리즘 설계는 문제가 없는거 같다.