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

그리디 알고리즘에 대해 공부한 뒤, 그리디 알고리즘 관련 첫번째 문제인 11047번 : 동전 0 을 풀었다.

 

그리디 알고리즘 에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/12

[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

 

 

---

<문제>

<문제 해석>

그리디 알고리즘을 이용하여 k원을 만드는데 동전의 최소 갯수를 구하라.

 

 

<문제 해결>

이 문제는 그리디 알고리즘만 이해하고 있으면 쉽게 풀 수 있는 문제라고 생각한다.

 

 

예제 문제 1번으로 설명을 해보겠다.

 

동전의 최소 갯수를 구하려면,

금액보다 작은 수들 중, 가장 큰 수부터 나눠서 최대한 금액을 줄여야한다.

 

금액이 4200원 이라면

4200원보다 작은 수들 중 가장 큰 수인 1000원으로 먼저 나눠야한다.

4200 / 1000 = 4

그리고 다음 금액은 4200 % 1000 인 200원이 된다.

 

200원보다 작은 수들 중 가장 큰수인 100원으로 나누면

200 / 100 = 2 가 되고

다음 금액은 200 % 100 = 0 이므로 더 이상 진행하지 않아도 된다.

 

총 동전의 갯수는 4 + 2 = 6개가 된다.

 

 

 

<알고리즘>

1.  다음 금액이 0이 될 때까지 진행

 

2. 금액보다 작은 수들 중 가장 큰수로 금액을 나눈 값 => 동전의 갯수

 

3. 다음 금액 : 금액 % 동전의 금액

 

 

 

<코드>

import java.io.IOException;
import java.util.Scanner;

public class Main {	

	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		int[] ar = new int[n];
		int count=0;
		for(int i=0;i<n;i++) {
			ar[i] = sc.nextInt();
		}
		
		for(int i=n-1;i>=0;i--) {
			if(ar[i] <= k) {
				count += k/ar[i];
				k = k % ar[i];
			}
		}
		
		System.out.println(count);

	}
}

 

그리디 알고리즘을 공부하고 난 뒤 문제를 풀어보니 훨씬 빠르고 쉽게 풀 수 있었다.

어떤 문제든 알고리즘이나 자료구조를 먼저 공부하고 이해한 뒤 풀어야한다.

다음으로 계속해서 그리디 알고리즘에 대한 문제들을 풀어보겠다.

 

---

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

11047번: 동전 0