[JAVA] BOJ(백준) - 동전 0 - 11047번

문제내용

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

11047번: 동전 0

준규가 가지고 있는 동전은 총 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. 전체 최적해가 부분 최적해도 만족해야한다.

2. 이전 선택이 이후 선택에 영향을 미치지 말아야한다.

위의 두가지 조건을 만족한다면 그리디 알고리즘으로 풀수 있고 그리디 알고리즘의 장점은 빠르다는것에 있다.

 

동전 0문제의 풀이 방법을 생각해보자.

돈 K를 최소개수의 동전으로 맞추기 위해선 가장 큰 단위부터 맞춰야한다는 것을 알 수있다.

예를들어 2000원의 경우 100원짜리 20개보단 500원짜리 4개가, 500원짜리 4개보단 1000원짜리 동전 2개가 낫다는 것을 알 수 있다.

마찬가지로 위의 문제에서도 4200원의 경우 1000원짜리 4개, 100짜리 2개로 총 6개의 동전으로 K를 만들 수 있다.

 

그럼 1000원짜리 4개를 뽑는 방법부터 생각해보자. 잘 생각해보면

입력받은 동전을 배열에 넣고 배열의 마지막 요소~0까지 탐색하며 배열 요소보다 K가 더커지거나 같아지는 순간이 K를 구성할 수 있는 동전의 가장 큰 단위라고 할 수 있다.

따라서 k/arr[i] -> 4200/1000 을 하면 1000원짜리 4개를 구할수 있고, 나머지 k%arr[i] -> 4200%1000 을 통해 k를 천원 짜리 4개를 뺀 200원으로 갱신할 수 있다.

그리고 갱신한 200원을 다시 위의 방법으로 반복해 풀면되는 것이다.

 

참고로 뒤에서부터 무작정 탐색할 수 있는이유는 입력받는 동전이 오름차순 정렬이 돼있기 때문이다.

안되있다면 정렬해주면 되긴함,

 

풀이를 보자

 

---

풀이

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

public class Main {
	static int[] arr;
	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());
		arr = new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		System.out.println(minCnt(N,K));
	}
	
	public static int minCnt(int n, int k) {
		int answer = 0;//최소 동전 개수
		for(int i=n-1; i>=0; i--) {
			if(k>=arr[i]) {
				answer += k/arr[i];
				k = k%arr[i];
			}
		}
		
		return answer;
	}
}

 

---

마치며

문제가 쉬워서 그런지 DP보다는 더 쉬운 느낌이다. 하지만 아직 그리디 알고리즘을 만족하는 조건을 생각하는건 더 연습해야 빠르게 판단이 가능할꺼라고 생각한다.