[알고리즘 풀이 분석] BOJ 13902 개업 2

오늘,, 아주 힘겹게 푼 문제는 BOJ 13902 개업 2 이다. 역시 오늘의 문제 에서 뽑아서 풀었고 골드 4 단계 문제이다. 아 문제를 풀 때 좀 더 신중하게 차근차근 접근하는 습관이 너무 부족 한 것 같다 ㅜ 하 제대로 집중해서 풀면 얼마든지 할 수 있는 것도 자꾸 놓치고,, 그러니까 집중력 흐려지고,, ㅜㅜ 속상하다,,

한번에 제출해서 "맞았습니다!!" 를 받는 연습을 남은 3주 동안 집중적으로 해야 할 것 같다!!

BOJ 13902 개업 2

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

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

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

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

입출력

나의 풀이

모든 경우의 수를 생각해야 하나,,? 고민하다가 그럼 아무래도 시간 초과를 면치 못할 것 같아서 DP 를 사용해야 겠구나 생각이 들었다!

주의깊게 문제를 읽지 않아 놓친 부분이 바로 "해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다." 이다!!!

M개의 웍이 주어질 때 M개 중에서 1~M개를 사용하는 경우를 모두 계산 해야 하나,,? 하면서 이건 너무 오래걸리는거 아닌가,,? 했는데,,
역시나 나의 실수 ^^,,,, 시방,,

M개의 웍중에서 한개 혹은 두개를 사용하는 경우 사용되는 웍의 총량을 배열 volume 에 저장하고 volume[i] 를 사용하여 dp 배열을 완성해 나가면 된다.

volume[i] 의 경우 주문된 양이 volume[i] 이상인 경우부터 적용 가능하므로 이부분 부터 두번재 중첩 for문을 돌리면 시간을 절약할 수 있다.

또한 주의해야 할 점이 탐색의 기준이 N이 아니라 volume이 되어야 한다는 점인데, 작은 volume 을 사용한 경우부터 먼저 고려해야만 큰 volume 을 사용하는 경우를 올바르게 도출할 수 있기 때문이다.

예를 들어, 위 그림처럼 volume이 3 이고 dp[4] 를 채우려는 경우 dp[4]는 3을 더해 4를 채우는 경우를 의미하기 때문에 1(4-3) 을 완성하는 최소 요리 횟수 dp[1] 이 필요하다. 이 때 만약 큰 volume 부터 채웠다면 dp[1]의 값은 채워지지 않은 상태이기 때문에 dp[4]를 올바르게 적을 수 없다!!

웍은 최대 두개까지만 동시에 사용가능한 점, 탐색의 기준이 작은 volume 부터인 점, 두가지만 조심하면 큰 어려움 없이 풀 수 있는 문제이다.

(근데 나는 왜 이렇게 오래 걸렸는가,,^_ㅠ,,
내일부턴 문제 풀기 전 주문처럼 천천히, 차분히,,, 주문 외우고 간다,,)

전체 코드

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

// BOJ 13902 개업 2, 골드 3, DP 사용,, 맞긴 맞았는데,,, ㅋ
using namespace std;

vector<int> wok;

vector<int> makeCombi(int N, int M){
    vector<int> volumes;

    vector<bool> selected(N+1, false);  // 웍의 양은 최대 N까지만 가능
    for (int i = 0; i < M; ++i) {
        selected[wok[i]] = true;
    }

    for (int i = 0; i < M; ++i) {
        for (int j = i+1; j < M; ++j) {
            int sum = wok[i] + wok[j];
            if(sum <= N && !selected[sum]) {
                selected[sum] = true;
            }
        }
    }

    for (int i = 1; i <= N; i++) {  // select 된 웍 용량 합 -> volume 에 옮기기
        if (selected[i]) volumes.push_back(i);
    }

    return volumes;
}

int getMinCook(vector<int> volume, int N){
    vector<int> dp(N+1, -1);
    dp[0] = 0;

    for (int i = 0; i < volume.size(); ++i) {  // 작은 양의 volume 부터 먼저 사용 
        int vol = volume[i];
        dp[vol] = 1;
        for (int j = vol+1; j <= N ; ++j) {  // volume 이상 부터 volume 적용 가능 
            if (dp[j-vol] == -1) continue;
            if (dp[j] == -1 || dp[j-vol] + 1 < dp[j]){
                dp[j] = dp[j-vol] + 1;
            }
        }
    }

    return dp[N];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin>>N>>M;

    wok.assign(M, 0);
    for (int i = 0; i < M; ++i) {
        cin>>wok[i];
    }

    vector<int> volume = makeCombi(N, M);  // 1개 혹은 2개의 웍을 사용할 때 웍의 양 저장

    int answer = getMinCook(volume, N);
    cout<<answer;

    return 0;
}