[백준] 13910번 : 개업 (C++)

13910번 : 개업

---

문제)

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

 

 

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

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

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

 

 

입력 :

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

 

 

 

출력 :

각 학기에 대해 근우의 총 학점과 평점(GPA)을 출력한다. 정답과의 절대 오차는 10-1까지 허용한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
vector<int> vec;
int dp[10100];
 
int recur(int cur)
{
    int ret = 10000000;
 
    if (cur == 0) return 0;
 
    // 답이 될 수 없음
    if (cur < 0) return 9999999;
 
    // 메모이제이션 적용
    if (dp[cur] != -1)
    {
        return dp[cur];
    }
 
    // 2중 for문을 이용하여 2개의 웍을 선택한다.
    for (int i = 0; i < m; i++)
    {
        for (int j = i + 1; j < m + 1; j++)
        {
            ret = min(ret, recur(cur - vec[i] - vec[j]) + 1);
        }
    }
 
    dp[cur] = ret;
 
    return dp[cur];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
 
    fill(dp, dp + 10100, -1);
 
    int a;
    for (int i = 0; i < m; i++)
    {
        cin >> a;
        vec.push_back(a);
    }
    // 요리를 할 수 없는 웍을 하나 더해준다.
    vec.push_back(0);
 
    int result = recur(n);
    
    
    // 나올 수 없는 값이 나온다면
    // 주문을 처리할 수 없으므로
    if(result >= 10000000)
    {
        cout << -1;
    }
    // 최소 요리 횟수를 출력한다.
    else
    {
        cout << result;
    }
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/13910 

13910번: 개업