백준 11047번 동전 0 (python, C++)

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

11047번: 동전 0

 

문제에서 N개의 줄에 동전의 가치가 오름차순으로 주어진다고 했으므로 N개를 입력받았을 때 가장 뒤에 있는 N-1인덱스에서 앞으로 갈수록 가치가 낮아진다. K원을 만드는데 필요한 최소한의 동전 갯수를 구해야 하므로 최대한 가치가 큰 동전을 많이 써야 한다. 

 

그러므로 [n-1]부터 [0]까지 차례대로 K원에서 각 원소를 뺐을 때 0보다 크거나 같으면 해당 원소의 동전을 몇 개까지 쓸 수 있는지 나누기를 통해 계산한 후 나머지는 다시 K에 넣어 K에서 이번에는 다음 원소 [n-2]를 뺀다.

이렇게 반복하다가 k에서 원소를 뺀 값이 0이 될 경우에는 나머지가 없으므로 계산이 끝나게 된다

(나머지가 안 생기는 이유는 이 조건 때문이다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수))

 

마지막으로는 그동안 계산해서 나온 값들을 더해서 나온 총 동전의 갯수 즉 최소한의 동전 갯수를 출력한다

.

<python>

n, k=map(int, input().split())
arr=[]
for i in range(n):
    a=int(input())
    arr.append(a)
  
min=0
for i in range(n):
    if k-arr[n-i-1] >= 0 :
        min=min+int(k/arr[n-i-1])
        k=k%arr[n-i-1]

print(min)   

 

 

<C++>

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	int n, k;
	int min = 0;
	cin >> n >> k;
	vector<int> coin(n);
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}
	for (int i = (n - 1); i >= 0; i--) {
		if (k - coin[i] >= 0) {
			min = min + k / coin[i];
			k = k % coin[i];
		}
	}
	cout << min;
}