[백준 11047] 동전0

동전 0

문제설명

첫 줄에 N,K를 입력 받고 N은 동전의 종류 수 이고, K는 맞추는 금액이다.
최소한의 동전으로 금액을 구성하여 필요한 동전 수의 최소 값을 출력시킨다.

---

알고리즘

1. 필요한 값들을 입력 받는다.
2. 최대한 빨리 찾기 위해서 오름차순으로 정렬된 동전들을 뒤 부터 조회한다.
3. 금액 K를 동전으로 나누어서 sum에 몫을 저장한다.
4. 나머지를 K에 다시 대입한다.
5. 반복문을 통해서 최소한의 동전을 구한다.

#include <iostream>
#include <stdio.h>

using namespace std;

int arr[11];
int main() {
	int n,k,cnt=0;
	cin >> n >> k;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
		for (int i = n-1; n>=0 ; i--)
		{
			if (k == 0)
				break;
			if (arr[i] <= k)
			{
				cnt = cnt+(k / arr[i]);
				k %= arr[i];
			}
		}
		cout << cnt;
}

---

고찰
다른 블로그들의 풀이 방식을 보니 DP로 접근하기도 하는데 DP는 메모리초과가 발생한다고 한다.
DP 공부하고 난 뒤 이 문제를 다시보면 헷갈리지 않을까 생각한다. 유형별로 차근차근 정리하는게 좋을 것 같다.