200번째 문제 - 13902 개업2

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

일반적인 동전 교환 dp 문제랑 많이 다르지 않다. 

화폐 단위 대신 웍의 크기를 사용하는데, 특이한 점은 동시에 두개를 들고 요리가 가능하단다...

그래서 서로 다른 웍의 크기를 더해 새로운 웍의 크기를 만들어주고 동적 계획법 하면 된다.

#include <iostream>

#include <algorithm>

#include <memory.h>

#include <string>

#include <vector>

using namespace std;

int  n,m,cache[10001]={0},t;

vector<int> size;

int main() {

cin>>n>>m;

for(int i=0; i<m; i++){ cin>>t; size.push_back(t);}

for(int i=0; i<m; i++)

{

for(int j=i+1; j<m; j++)

{

//두개를 동시에 들고 요리하는 경우 고려

size.push_back(size[i]+size[j]);

}

}

sort(size.begin(), size.end());

unique (size.begin(), size.end());

for(int i=1; i<=n; i++)

{

cache[i]=987654321;

for(int j=0;j<size.size();j++)

{

if(i-size[j]>=0) cache[i] = min(cache[i],cache[i-size[j]]+1);

else break;

}

}

if(cache[n]==987654321) cout<<-1;

else cout<<cache[n]<<endl;

}