백준 11047번 자바

문제

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

11047번: 동전 0

 

1. 접근방식

전형적인 그리디 방식의 문제다. 

그리디 문제에서 가장 중요한 점은 매 분기에서 가장 좋은 선택을 하며, 이전 선택의 결과가 이후 선택의 결과에 영향을 미치지 않는다는 것이다.

 

해당 문제의 경우 

임의의 동전의 가치 Ai로 K원을 나눴을 때 몫이 1이상인 경우를 먼저 찾은 뒤 

몫 x Ai원을 K원에서 빼준다. 이후엔 같은 방식으로 해결하면 된다.

 

예제를 기준으로 1000원을 선택하고 K원에서 나눠준 몫 4를 곱해준다.

K원에서 4000원을 빼준 뒤 남은 200원에서 동전의 가치가 100원인 동전을 선택한다.

이전 선택인 1000원이 다음 선택인 200원에 영향을 주지 않는다.

 

 

2. 구현

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

public class Main11047 {
	static int N,K;
	static int[] coins;
	static int max;
	static int cnt;

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

 

정리 :

어렵지 않게 풀었으나 다른 코드들을 보니 내가 만든 코드를 더 간결하게 만들 수 있는 방법이 있었다.

내 코드의 경우 몫만큼 반복문을 돌리기에 범위값이 커지면 그 만큼 더 많은 시간이 더 소요된다.

연산 한번으로 끝낼 수 있는 부분을 반복문으로 돌렸기에 반쪽짜리 통과라 생각이 든다..

아래에 해당 부분을 첨부해 복기하자.

for(int i = N - 1; i >= 0; i--) {
 
			// 현재 동전의 가치가 K보다 작거나 같아야지 구성가능하다.
			if(coin[i] <= K) {
				// 현재 가치의 동전으로 구성할 수 있는 개수를 더해준다.
				count += (K / coin[i]);
				K = K % coin[i];
			}
		}
출처 : https://st-lab.tistory.com/143