[백준] 11047번: 동전 0

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

11047번: 동전 0

Greedy 방식으로 푸는 전형적인 방식인데, 예시 입출력에서 보이지 않는 예외적인 상황들을 고려하기가 관건이다.

 

(A) k가 동전 최대값보다 큰지, 작은지

(B) 동전이 1개(1짜리)만 주어질 경우

 

기본적인 아이디어는

k보다 작은 동전들중 가장 큰 동전을 빼고, k-그 동전을 해서 k가 0이 될 때까지 돌리면 되는 거라고 생각했는데, 생각해보니까, k가 가장 큰 동전보다 큰 경우는 가장 큰 동전을 빼줘야 한다.

 

(A) k가 동전 최대값보다 큰지, 작은지

내가 헤맸던 파트는

while(k>0){
		
		int target = 0;
		
		if(v.size()==1){
			count = k/v[0];
			break;
		}
        
		// 자기보다 작은 값 중 제일 큰 값 
		for(int i = 0; i<v.size(); i++){
			if(v[i]>k){
				target = v[i-1];
				break;
			}
		}
		
		//cout << "minus: " << target << endl;
		k = k-target;
		count++;
	}

k가 가장 큰 동전보다 클 수 있다는 것을 생각하지 않았다는 것이다.

 

이걸 먼저 고려하고, 만약 k가 가장 큰 동전보다 작은 값이라면 자기보다 작은 값 중 제일 큰 값을 찾아서 계속 빼주는 식으로 답을 구하면 된다. 

	while(k>0){
		
		int target = 0;
		
		if(v.size()==1){
			count = k/v[0];
			break;
		}
		// k가 가장 큰 동전보다 큰 값인지 확인
        	// 만약 그렇다면 가장 큰 동전을 빼줘야 한다.
		if(v[v.size()-1]>k){
			target = v[v.size()-1];
		}
        
		// 자기보다 작은 값 중 제일 큰 값 
		for(int i = 0; i<v.size(); i++){
			if(v[i]>k){
				target = v[i-1];
				break;
			}
		}
		
		//cout << "minus: " << target << endl;
		k = k-target;
		count++;
	}

사실 내가 제일 처음에 답으로 제출해서 맞은 코드는

while(k>0){
		// 자기보다 작은 값 중 제일 큰 값 
		int target = 0;
		
		if(v.size()==1){
			count = k/v[0];
			break;
		}
		
		for(int i = 0; i<v.size(); i++){
			if(v[i]>k){
				target = v[i-1];
				break;
			}
		}
		
		// 루프를 다 돌았는데, target값이 지정이 안됐다는 건, k가 가장 큰 동전보다 크다는 것
        	// 그래서 target을 가장 큰 동전으로 지정해준다. 
		if(target == 0){
			target = v[v.size()-1];
		}
		
		
		//cout << "minus: " << target << endl;
		k = k-target;
		count++;
	}

이거였다. 근데 코드를 다시 보니까 for()을 돌리기 전에, 우선 k가 가장 큰 동전보다 큰 값인지 확인하는데 더 효율적이라 최종 답안은 바꿨다. 

 

(B) 동전이 1개(1짜리)만 주어질 경우

또 하나 중간에 빼먹을 뻔한 것이, 

if(v.size()==1){
	count = k/v[0];
	break;
}

이 부분이었다. 

만약 동전이 1짜리 하나밖에 없다면 for()문에서 target을 구할 때 v[i-1]을 구할 수 없다. 

그래서 n=1일 경우에는 그냥 k를 1로 나누어버린 값을 출력하면 답이 된다. 

 

예제 입력

내가 이런 예외들을 잡아낸 예제 입력을 남긴다.

예제 입력 (A)

9 4200

1

2

3

4

5

6

7

8

9

 

예제 입력 (B) 

1 10

1

 

최종 제출 코드

// 11047

#include <iostream>
#include <vector>

using namespace std;

int main(void){
	
	int n, k;
	vector<int> v;
	int count = 0;
	
	cin >> n >> k;
	for(int i = 0; i<n; i++){
		int temp;
		cin >> temp;
		v.push_back(temp);
	}
	
	while(k>0){
		
		int target = 0;
		
        // (B) 동전이 하나만 주어진 경우
		if(v.size()==1){
			count = k/v[0];
			break;
		}
		
        // (A) k >= 가장 큰 동전
		if(v[v.size()-1]>k){
			target = v[v.size()-1];
		}
		
		for(int i = 0; i<v.size(); i++){
			if(v[i]>k){
				target = v[i-1];
				break;
			}
		}
		
		k = k-target;
		count++;
	}

	cout << count << endl;
	return 0;
	
}