백준 - 11047번 : 동전 0 (C++)

풀이 방법 : 그리디

처음에 제한사항도 안보고 그냥 DP겠거니 하고 대충 풀었다가 메모리 초과가 떴었다. K의 최댓값이 1억이기 때문에 DP 배열을 1억개나 할당해버리면 메모리 제한을 넘겨버리기 때문이었다.

그래서 어떻게 풀어야하나 하다가
두번째 조건에서 첫번째 입력은 무조건 1이라고 주어져있기 때문에 K를 만들지 못하는 경우는 없다. 그러므로 큰 액수의 동전부터 K를 나눠가면서 동전의 수를 체크하면 되겠다고 생각했다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N >> K;

	vector<int> vecNum(N);

	for (int i = 0; i < N; ++i)
	{
		int Num;
		cin >> Num;

		vecNum[N - 1 - i] = Num;
	}

	int Cnt = 0;

	int CurrentNum = K;
	
	for (int i = 0; i < N; ++i)
	{
		if (CurrentNum == 0)
			break;

		if (CurrentNum < vecNum[i])
			continue;

		Cnt += CurrentNum / vecNum[i];
		CurrentNum %= vecNum[i];
		
	}

	cout << Cnt;
}

항상 입력의 최댓값을 확인하고 풀이하자..