백준 11047 동전0_그리디

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

11047번: 동전 0

 

아주 직관적으로 풀어보았다.

#include <iostream>

using namespace std;

int N;
int K;
int arr[1000001] = { 0, };

int main() {
cin >> N >> K;
for (int i = 1; i < N+1; i++) {
cin >> arr[i];
}
    int cnt = 0; //최소 동전 개수 
    int current = 0; 
    int sum = 0; 
    
    while (1) {
    	sum = 0;
    	for (int i = 1; i < N + 1; i++) {
    		if (arr[i] > K) {
    			current = i - 1; // K보다 작은 수 중 가장 큰 수 찾기
    			break;
    		}
    	}
    	while (sum <= K) { // 가장 큰 동전이 몇 개 필요한지 확인
    		sum += arr[current];
    		cnt++;
    	}
    	sum -= arr[current];
    	cnt--; // 마지막 동전을 한번 더 더했으므로 빼주기
    
    	K = K- sum; // 값 갱신
    	if (K== 0) break; //동전을 모두 더해서 값이 0이 되었으면 반복문 탈출
    
    }
    cout << cnt;

}

정말 효율적이지 못한 코딩. 예제는 통과하지만 제출 시 시간 초과 난다.

 

https://m.blog.naver.com/PostView.nhn? blogId=occidere&logNo=220802824513&proxyReferer=https% 3A% 2F%2Fwww.google.com% 2F

[백준] 11047 - 동전 0

​

을 참고하였다.

 

#include <iostream>

using namespace std;

int N;
int K;
int M = 0;
int arr[1000001] = { 0, };

int main() {
	cin >> N >> K;
	for (int i = 1; i < N+1; i++) {
		cin >> arr[i];
	}

	for (int i = N; i > 0; i--) {   // ex) 4200 원에서 
		M += K / arr[i];		  // arr[i] 가 4200 보다 크면 0이 더해짐.
							//arr[i] 가 K 보다 작으면 4200 / 1000 => 4 (횟수) 가 M에 더해짐
		K = K % arr[i];		// 4200 % 1000 이면 나머지 200 원이 K에 갱신 
						   //만약 4200 % 5000 이였으면 나머지인 4200 그대로
	}
	cout << M;
}

4200 / 1000 * 4에서 4가 최소 연산 횟수에 더해질 것이다.

남은 200에서는 100 * 2에서 2가 최소 연산 횟수에 더해질 것이다.

​

/, % 을 사용하여 아래와 같이 깔끔하게 정리가 가능하다.

 

 

​