[C++/알고리즘] 백준 11047 (동전0)

11047번: 동전 0 (acmicpc.net)

11047번: 동전 0

 

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

int N, K;
vector<int> value;
int func()
{
	int answer = 0;
	int i = N-1;
	do {
		answer += (K / value[i]);
		K %= value[i];
		--i;
	} while (i >= 0);

	return answer;
}

int main()
{
	cin >> N >> K;
	int temp = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		value.push_back(temp);
	}
	cout << func();
}

 

Greedy 알고리즘 문제로 간단하게 풀 수 있는 문제이다.

완전탐색을 진행하더라도 N번. 즉 10번만 돌면 되기 때문에 시간복잡도가 O(N)이다.

 

요즘 자꾸 주어진 케이스가 1개일 때 예외처리를 자꾸 빼먹는다. 문제 풀기 전에는 분명 꼭 1개일 때도 고려해야된다고 세번씩 다짐하지만 어느순간 잊는다.그래서 맨 위에 앞으로 주석으로 // N = 1개 일 때? 라고 추가하기로 했다.절대 안 볼 수 없게 특수문자 왕창 넣어 놔야지