행운쿠키 제작소( BOJ 10982 )

문제 : https://www.acmicpc.net/problem/10982

10982번: 행운쿠키 제작소

 

문제 파악하기

2개의 오븐을 사용해 모든 행운쿠키를 굽는데 걸리는 최소 시간을 구하는 문제입니다. 쿠키는 어떤 오븐에서 굽는지에 따라 완료되는 시간이 다르기에 쿠키마다 오븐을 적절하게 활용해야 효율적으로 모든 쿠키를 구울 수 있습니다. 전형적인 배낭 문제의 한 종류로, 동적 프로그래밍 기법을 활용하면 어렵지 않게 문제를 해결할 수 있습니다.

 

문제 해결하기

이 문제에서 중점으로 봐야할 핵심요소는 바로 모든 쿠키는 항상 오븐에 넣어야 한다는 점입니다. 어찌되었든 쿠키들은 오븐 A, B 중 한 곳에서 구워져야하며 우리는 이 점에 주목하여 다음과 같이 배열을 하나 생성할 수 있습니다.

 

dp[tA][tB] // 오븐 A을 tA만큼 사용하고, 오븐 B를 tB만큼 사용한 경우의 가능 여부

>> dp[tA][tB]가 1이면 가능 / 0이면 불가능

 

위의 배열은 다만 문제가 한 가지 있습니다. tA와 tB 모두 최대 100,000까지 늘어날 수 있기 때문에 2차원 배열로 선언할 수 없습니다. 따라서. 위의 배열의 차원을 줄일 필요가 있으며, 보통 dp[tA][tB] 배열과 같이 배열에 저장하는 값이 [ 가능/불가능 ] 혹은 [ 참/거짓 ]인 경우에는 매개변수의 값을 배열에 넣어줄 수 있습니다. 따라서, 우리는 dp[tA][tB] 배열을 다음과 같이 재선언할 수 있습니다.

 

dp[tA] // 오븐 A를 tA만큼 사용했을 때, 오븐 B를 사용한 시간의 최솟값

 

dp 배열을 위와 같이 바꿔주면 한 번에 정답을 구할 수는 없지만 tA와 dp[tA]의 값을 활용하여 문제를 충분히 해결할 수 있습니다. 이렇게 배열을 선언하였다면 남은 일은 관계를 파악하여 배열을 올바르게 채워주는 일입니다. 그렇다면 어떻게 배열을 채워줄 수 있을까요?

 

우선, N개의 쿠키를 모두 오븐에 넣어야 하기 때문에 N번 반복하는 반복문이 필요합니다. 그 다음으로 필요한 걸 떠올리기 위해서는 dp 배열을 어떻게 순회하면서 채울 수 있을지 고민해야 합니다. 우리는 모든 경우에서 생각해보아야 하기에 0부터 모든 쿠키를 오븐 A에 넣었을 때의 시간(tot)까지 항상 확인해야 하기에 tot번 반복하는 반복문도 필요합니다. 그럼 우리는 총 2개의 반복문이 필요하며, 이 반복문을 모두 확인한 다음에는 문제를 해결할 수 있는 dp 배열이 완성될 것이라고 판단할 수 있습니다.

 

그럼 이제 마지막 단계는 dp 배열을 어떻게 채울지 고민해야 합니다. 만약 i번째 쿠키를 탐색하는 과정이라면 dp[ idx ]는 오븐 A에 넣는 경우와 오븐 B에 넣는 경우로 비교할 수 있습니다. 오븐 A에 넣는 경우에는 인덱스(idx)를 증가/감소시켜 dp[ ]의 값을 활용할 수 있으며, 오븐 B에 넣는 경우에는 dp[ idx ] + (i번째 쿠키의 오븐 B 시간) 값을 활용할 수 있습니다. 오븐 B를 사용하는 건 어렵지 않게 구할 수 있습니다. 그럼 오븐 A를 사용하는 건 맘에 드는 걸 선택하면 될까요?

 

여기서 놓치지 말아야 할 건 바로 현재 탐색하는 상태가 중복으로 영향을 받으면 안 된다는 점입니다. 현재 탐색하는 상태는 배열에서 채우는 위치를 의미하며, 배열에서 채우는 위치는 하나의 쿠키를 확인할 때에 여러 번 영향을 미치면 안 됩니다. 따라서, 현재 확인하는 i번째 쿠키에서 아직 탐색하지 않은 배열의 값을 변경시키지 않도록 점화식을 설계하면 문제를 정확하게 해결할 수 있습니다. 만약 반복문이 tot에서 0의 역순으로 진행된다면 dp[ ] 배열의 값은 다음과 같이 채울 수 있습니다.

 

dp[ idx ] = min( dp[ idx - inp[i].first ], dp[ idx ] + inp[i].second ) // inp[i] = { 오븐 A 시간, 오븐 B 시간 }

 

다만, 점화식을 보면 예외처리가 필요한 경우가 보입니다. idx의 값이 만약 inp[i].first 값보다 작다면, 즉 탐색한 시간(idx)이 오븐 A로 현재 쿠키( i )를 굽지 못하는 경우에는 무조건 오븐 B에 넣어주어야 합니다. 또한, 우리는 최솟값을 구하기 때문에 배열에는 최댓값인 대략 100,000보다 큰 숫자를 넣어주면 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#import <stdio.h>
#import <vector>
#import <utility>
#import <algorithm>
#define NMAX 100010
#define PAIR pair<int, int>
using namespace std;
 
int T, N, a, b;
vector< PAIR > inp;
 
int tot, ret;
int dp[NMAX];
 
int main() {
    scanf("%d", &T);
    while(T--) {
        // 초기화
        inp.clear();
        for(int i=0;i<=tot;i++) dp[i] = NMAX;
        
        tot = 0;
        ret = NMAX;
        
        // 입력
        scanf("%d", &N);
        for(int i=0;i<N;i++) {
            scanf("%d %d", &a, &b);
            
            inp.push_back({a, b});
        }
        
        // dp[idx]: 오븐 A로 idx분 사용했을 때, 오븐 B의 최소 시간
        dp[0] = 0;
        for(int i=0;i<N;i++) {
            tot += inp[i].first;
            
            for(int idx=tot;idx>=0;idx--) {
                if(idx >= inp[i].first) dp[idx] = min( dp[idx-inp[i].first], dp[idx]+inp[i].second );
                else dp[idx] = dp[idx] + inp[i].second;
                
                // 가장 오래 걸리는 오븐의 최솟값 찾기
                if(i == N-1) ret = min( ret, max(idx, dp[idx]) );
            }
            
        }
        
        // 출력
        printf("%d\n", ret);
    }
}
 

후기

전형적인 배낭 채우기 문제 유형 중 하나로, 점화식을 설계하는데 생각이 필요했던 문제입니다. 배열의 크기를 2배로 늘리면 좀 더 쉽게 점화식을 설계할 수 있지 않을까 생각이 듭니다. 항상 드는 생각이지만 배낭 문제가 가장 재미있는 유형이라고 생각합니다. 동적 프로그래밍을 연습하는 사람들에게 추천하는 문제입니다.