골드4 - 백준 13902 개업2

백준 13902 개업2

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

접근방법

두 손을 이용해 한번에 처리할 수 있는 주문의 수를 전부 구하고, 동적 프로그래밍을 이용하여 1개의 주문부터 N개의 주문까지 차례대로 증가해면서 이미 저장된 이전 값을 활용하여 N개의 주문을 처리하는데 필요한 최소값을 구해주었다.

풀이

이중 반복문을 통해 두 손을 이용할 때 처리할 수 있는 모든 경우를 bool comb배열을 통해 true로 체크해주었다. comb 배열을 순차적으로 돌면서 true로 체크되어 있는 수를 com 벡터에 넣어주어 중복을 제거해주었다.
1부터 N까지 1씩 증가시키면서 dp 배열을 채워주었는데, com에 저장되어 있는 모든 수를 현재 수에서 빼주어 이전 dp값에 1을 더해주었고 그중에서 최소값을 구해 dp배열에 저장해주었다.
이렇게 N까지 반복문이 진행되었을 때, dp[N]에 저장되어 있는 값이 만약 초기값인 100000이라면 -1을 출력하고 이외의 값이 있다면 해당 값을 출력해주었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> pan;
int dp[10001];
vector<int> com;
bool comb[20001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, S;
	cin >> N >> S;

	for (int i = 0; i <= N; i++)
		dp[i] = 100000;

	for(int i=0; i<S; i++)
	{
		int p;
		cin >> p;
		pan.push_back(p);
	}

	for (int i = 0; i < S; i++)
	{
		comb[pan[i]] = true;

		for (int j = i + 1; j < S; j++)
			comb[pan[i] + pan[j]] = true;
	}

	for (int i = 0; i < 20001; i++)
	{
		if (comb[i])
			com.push_back(i);
	}

	sort(com.begin(), com.end());
	dp[0] = 0;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < com.size(); j++)
		{
			if (i - com[j] >= 0)
				dp[i] = min(dp[i - com[j]] + 1, dp[i]);
			else
				break;
		}
	}

	if (dp[N] == 100000)
		cout << -1 << endl;
	else
		cout << dp[N] << endl;

	return 0;
}