[백준] 11047번: 동전 0 [JAVA]

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

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

알고리즘

이번 문제는 K값에 필요한 동전 개수의 최소값을 구하는 문제입니다.

가장 최적의 해를 구하는 방법인 탐욕(Greedy) 알고리즘입니다.

 

문제 풀이 방식은

동전의 종류는 오름차순으로 주어지므로

역순(동전 값이 큰 수)으로 동전을 K값과 비교하며 K값보다 가장 가까우면서 작은 값을 차감하며 진행합니다.

동전의 가치를 A라고 하면

차감하는 방식은

횟수는 K에서 A를 뺄 때 1씩 증가시키고,

K는 K에서 A를 뺀 수를 대입합니다.

 

하지만, 빼기로 진행하여 같은 값을 여러 번 뺀다면 효율적이지 못하므로

같은 값으로 빼게 되는 경우를 생각하여

횟수는 K를 A로 나눈 값의 몫을 더하고,

K는 K를 A로 나눈 나머지를 대입합니다.

 

예시로 K가 3200이고 A가 1000일 때,

3200에서 1000을 3번을 빼면 200이 남고 다음 동전으로 넘어가지만

3200을 1000으로 나누면 몫이 3, 나머지가 200이므로 행동 한 번으로 횟수와 남은 K가 효율적으로 구해집니다.

---

코드

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

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[] coins = new int[N];
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			coins[i] = Integer.parseInt(br.readLine());
		}
		
		for(int i = N-1; i >= 0; i--) {
			if(coins[i] <= K) {
				cnt += K/coins[i];
				K %= coins[i];
			}
			if(K == 0)
				break;
		}
		System.out.println(cnt);
	}
}

---

이번 문제를 풀면서 처음에 빼는 방식으로 진행했지만 시간이 212ms 가 나왔다.

맞은 문제들을 보니 120ms 이길래 내가 비효율적으로 풀었다고 생각했고, 빼는 방식을 나누는 것으로 진행하면 훨씬 효율적으로 진행할 수 있다고 생각하여 풀어보니 128ms가 나왔고, 그 후 다른 사람들의 코드를 보니 두 번째로 푼 방식이 효율적으로 작성했다는 것을 알았다.

이 글의 알고리즘이나 코드에서 지적할만한 부분은 댓글에 남겨주시면 저에게 많은 힘이 됩니다!