[백준알고리즘-JAVA]11047번 풀이(동전0) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 11047번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

입력 예제

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

출력 예제

6

입력 예제

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

출력 예제

12

성공 코드

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

public class Main {

	static int N;
	static int K;
	static int[] value;
	
	static int ans = 0;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		value = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			value[i] = Integer.parseInt(br.readLine());
		}
		
		
		for(int i = N -1 ; i >= 0 ; i--) {
			if(K / value[i] >= 1) {
				ans += K/value[i];
				K = K%value[i];
			}
		}
		
		System.out.println(ans);
		
		}

}

동전 0 알고리즘은 굉장히 풀기 쉬웠습니다. 뭐 사실 그리디 알고리즘이란 것을 처음 접해보고 풀어봤는데 아직까지 그리디 알고리즘이 무엇을 의미하는지는 잘 모르겠습니다.

 

그러나 이러한 신기한 점은 있다는 것 알아두세요!

 

 - 그리디 알고리즘으로 풀 수 있는 문제는 다이내믹 프로그램밍으로 풀 수 있다.

 - 다이나믹 프로그래밍으로 풀 수 있는 문제는 그리디 알고리즘으로 풀 수도 아닐 수도 있다.

 

이제 STEP을 따라가며 이해해 봅시다.

---

알고리즘 흐름도

입력받기 ->  큰돈부터 나누어 목과 나머지 알아내기 -> 반복하여 답 구하기 -> 출력하기

 

---

STEP1 문제 이해하기

 문제에서 원하는 답은 동전 개수의 최솟값을 구하고 싶어 합니다. 저 같은 경우는 바로 떠올렸습니다. 가장 큰 수부터 사용할 수 있으면 사용하고 그다음 큰 수로 넘어가면 되지 않을까?

 

 저희가 평시에 사용하는 500원, 1000원 이 있다고 가정한다면

1500원은 천 원 한 장 오백 원한장 이렇게 2장이 최소가 되겠죠. (오백 원 3개 보다는 적다)

 

이러한 아이디어가 있다면, 바로 쉽게 다음 STEP으로 넘어가면 됩니다.

---

STEP2 반복문 구현하기

 이제 큰 수부터 나누어주도록 FOR문을 작성해 봅시다.

for(int i = N -1 ; i >= 0 ; i--) {
		}

주어진 입력은 오름차순으로 되어있으니 N-1즉 가장 뒤쪽부터 탐색을 시작합니다.

 

for(int i = N -1 ; i >= 0 ; i--) {
			if(K / value[i] >= 1) {
				
			}
		}

K는 여기서 처음 입력받았던 가치의 합입니다.

 

K가 그 가치로 나누었었을 때 몫이 1 이상이라면~

 

이 의미는 비교하려는 VALUE [i] 보다 값이 크다는 의미가 되겠죠 그렇다면 그 숫자만큼 차감해 줍니다.

for(int i = N -1 ; i >= 0 ; i--) {
			if(K / value[i] >= 1) {
				ans += K/value[i];
				K = K%value[i];
			}
		}

정답에는 그 몫을 넣어줍니다. => 여기서 몫이 의미하는 것은 바로 돈의 개수

 

K에는 나머지를 넣어줍니다. => 여기서 나머지가 의미하는 것은 큰돈으로 합을 뺀 나머지 가치의 합

 

이런 식으로 구현만 해준다면, 이번 문제는 아주 쉽게 풀이가 됩니다.

---