글 작성자: Sowhat_93
BOJ 13902 개업 2

동적계획법을 이용하면 쉽게 해결이 가능한 문제이다.

웍의 경우는 동시에 2개를 사용이 가능하므로, 웍의 조합으로 새로운 크기의 웍을 만들고

반복문을 이용해 동적계획법을 사용한다.

 

N 그릇을 요리한다고 할때, 내가 가진 웍의 크기가 각각 3 4 5 6 이라고 하자.

그렇다면 요리횟수의 최소값은

(N - 3) 그릇을 요리하는 회수 + 1

(N - 4) 그릇을 요리하는 회수 + 1

(N - 5) 그릇을 요리하는 회수 + 1

(N - 6) 그릇을 요리하는 회수 + 1 

중 하나이다.

 

코드로 구현하면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
std::vector<int> Works;
bool WorkHave[20001] = { false, };
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int MinLabor[10001] = { 4, };
int NumOrder;
int NumWorks;
int WorkSize;
std::cin >> NumOrder;
std::cin >> NumWorks;
for (int i = 0; i < NumWorks; ++i)
{
std::cin >> WorkSize;
Works.push_back(WorkSize);
}
for (int i = 0; i < NumWorks; ++i)
for (int j = i + 1; j < NumWorks; ++j)
{
int DualWorkSize = Works[i] + Works[j];
if (WorkHave[DualWorkSize] == false)
{
Works.push_back(DualWorkSize);
WorkHave[DualWorkSize] = true;
}
continue;
}
sort(Works.begin(), Works.end());
auto U = unique(Works.begin(), Works.end());
Works.erase(U, Works.end());
for(int i = 1 ; i <= NumOrder; ++i)
MinLabor[i] = 10001;
MinLabor[0] = 0;
size_t HMWorks = Works.size();
for (int i = 0; i < HMWorks; ++i)
{
int SelectedWorkSize = Works[i];
for (int j = SelectedWorkSize; j <= NumOrder; ++j)
{
int Pre = j - SelectedWorkSize;
if (MinLabor[j] > MinLabor[Pre] + 1)
MinLabor[j] = MinLabor[Pre] + 1;
}
}
if (10001 == MinLabor[NumOrder])
std::cout << -1;
else
std::cout << MinLabor[NumOrder];
return 0;
}