[BOJ] 개업 13910번 C++

 

 

문제

해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 해빈이는 낭비를 매우 싫어하기 때문에 요리 할 때, 필요 이상 크기의 웍을 사용하지 않으며, 주문 받은 짜장면의 그릇 수에 딱 맞게 요리한다.

<웍>

예를 들어 짜장면 4그릇을 주문 받았는데 5그릇 이상을 요리하지 않으며, 4그릇을 요리할 수 있는 웍에 3그릇 이하의 요리를 하지 않는다.

해빈이가 5그릇을 주문 받았고, 해빈이가 가지고 있는 웍의 종류가 1, 3그릇 용이라면 처음에 1,3그릇용 웍을 동시에 이용하여 4그릇을 만들고 다음 1그릇용 웍을 이용하여 1그릇을 만들어 총 5그릇을 두 번의 요리로 만들 수 있다.

해빈이가 주문 받은 짜장면의 수와 가지고 있는 웍의 크기가 주어질 때, 최소 몇 번의 요리로 모든 주문을 처리할 수 있는지 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 해빈이가 주문 받은 짜장면의 수N(1≤N≤10,000)과 가지고 있는 웍의 개수 M(1≤M≤100)이 주어진다. 두 번째 줄에는 웍의 크기 Si(1≤Si≤N)이 M개가 주어지며 같은 크기의 웍을 여러 개 가지고 있을 수 있다.

출력

해빈이가 모든 주문을 처리하기 위해 해야 하는 최소 요리 횟수를 출력한다. 만약 모든 주문을 처리 할 수 없는 경우 -1을 출력한다.

 

접근 방식

 

dp[i]를 i개의 짜장면을 만드는 최소 요리 횟수로 정의한다

이때, 혜빈이는 손이 두개로 웍을 최대 2개까지 동시에 요리할 수 있다

따라서, 웍 하나를 사용한다면 dp[i-S]+1

웍 두개를 동시에 사용한다면 dp[i-(S1+S2)] +1을  비교해서 최소값을 갱신하면 된다!

 

 

코드

#include<bits/stdc++.h>
using namespace std;
int dp[100003];
constexpr int INF = 1e9;
int main() {
    int N,M; cin>>N>>M;
    vector<int> v(M);
    for(int i=0; i<M; i++) {
        cin>>v[i];
    }

    fill(dp, dp+N+1, INF);
    dp[0] = 0;

    for(int i=0; i<M; i++) {
        for(int j=v[i]; j<=N; j++) {
            dp[j] = min(dp[j], dp[j-v[i]]+1);
        }
    }

    for(int i=0; i<M; i++) {
        for(int j=i+1; j<M; j++) {
            int sum = v[i] + v[j];
            if(sum <= N){
                for(int k=sum; k<=N; k++) dp[k] = min(dp[k], dp[k-sum]+1);
            }
        }
    }

    if(dp[N]==INF) cout<<-1;
    else cout<<dp[N];
    
}