백준 / 그리디 알고리즘 / 11047번 / 동전 0 / C++

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1

10 4200

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 1

6

예제 입력 2

10 4790

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 2

12

 

#include <iostream>
using namespace std;

int main() {
	int n, k;
    int cnt = 0;
    int arr[10] = {0};
    
    cin >> n >> k;
    
    for(int i=0; i<n; i++) {
    	cin >> arr[i];
    }
    
    for(int i=n-1; i>=0; i++) { // 가장 큰 동전의 액수부터
    	cnt += k / arr[i];
        k %= arr[i];
    }
    
    cout << cnt << endl;
}

---

사실 처음에 그리디 알고리즘에 대해서 모르고 풀었을때랑 별반 차이 없었다.

그리디 알고리즘이란 매 순간마다 최선의 조건만을 선택하는 방법이다.

 

따라서 위코드의 마지막 for문을 보자면, 입력받은 배열의 끝부터 시작해서 0까지 반복문 사이클이 돈다.

cnt += k / arr[i]를 보자.

예제 입력1 로 예시를 들면, 4200 / 50000부터 하는거다.

그럼 cnt의 값은 0이나온다.

그리고 다음줄인 k %= arr[i]를 보면, 4200 % 50000을 하면 4200이 그대로 남게된다.

그렇게 쭉쭉 50000,10000,5000,1000순으로 i--시키면서 하다보면 1000으로 드디어 나눌 수 있게된다.

4200 / 1000을 하면, 4200원은 4개의 1000원이 들어가니깐 4가 되고,

다음줄로 넘어가서 4200 % 1000을 하게 되면 200이 남는다.

그리고 i--계속하면서 100으로 또나뉘어져서 cnt에 2가 더해지고, k는 0이된다.

우리가 구할값은 다 구했지만, 반복문은 arr[i]까지 계속 돌게된다.

 

사실 알고리즘을 생각하는덴 별 무리없었지만, 내 생각을 코드로 옮기는데에 while문으로 해결하려다 보니 시간초과가 떴었고, for문으로 풀게되었다.

만약 오류가 나지 않는 while문으로 풀게되면 반복횟수는 k값이 1단위가 아닌이상 적어지게 될것이다.