[백준 1493 - C++] 박스 채우기 : 분할 정복

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

1493번: 박스 채우기

 

문제

세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)

세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 세 자연수 length width height가 주어진다.

둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.

셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.

출력

첫째 줄에 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.

제한

• 1 ≤ length, width, height ≤ 10^6
• 1 ≤ n ≤ 20
• 0 ≤ Ai < 20
• 0 ≤ Bi ≤ 10^6
• Ai ≠ Aj (i ≠ j)

예제 입력 1

4 4 8

3

0 10

1 10

2 1

예제 출력 1 

9

 

 풀이

이 문제는 아이디어는 어렵지 않다. 위 그림에서 빨간색 큐브를 넣는 다고 하면 나머지 빈 공간을 직육면체로 나타내기가 쉽지않다.

따라서 이 공간을 3개로 나눠준다. 위 그림처럼 주황색, 연두색, 파란색 이렇게 3개로 나눠서 재귀를 호출하는 것이다.

이 때 가장 적은 수의 큐브를 넣어야 하기 때문에 우선은 크기가 큰 큐브부터 박스에 넣어주는 식으로 코드를 짜면 된다.

 

그래서 일단 저 아이디어 대로 코드를 휘릭 짰는데 미친듯한 시간초과를 마주했다..ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

몇번을 도전해도 60퍼 쯤에서 어김없이 등장하는 시간초과...ㅋㅋㅋㅋㅋㅋ

진짜 이 정도면 채점이 잘못되고 있는건가 싶어서 구글링해서 다른 분 코드를 돌려봤는데 잘나오더라... 내 코드랑 별 차이도 없는데ㅠ

 

사실 나는 재귀를 호출할 때 이렇게 호출하고 있었다.

sol(l-pow(2, c_idx), w, h, c_idx);
sol(pow(2, c_idx), w, h-pow(2, c_idx), c_idx);
sol(pow(2, c_idx), w- pow(2, c_idx), pow(2, c_idx), c_idx);

여기서 문득 '와.. 설마 저 제곱 구하는데 시간이 오래걸려서 그런건가?' 여러번 계산하지 말고 변수에 넣어서 하면 시간초과가 안나려나...?' 하는 생각이 들었다.

그래서 하나의 변수에 저장하고 사용하니까 진짜 금방 끝난다....

잊지말자. 짧은 계산이라도 코드에 쌓이면 엄청난 결과를 초래한다는 것을ㅠㅠㅠ 티끌 모아 태산이더라...

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int cube[21];

long long cnt;

void sol(int l, int w, int h, int c_idx){
    //printf("%d %d %d %d %lld\n", l, w, h, c_idx, cnt);
    int flag = 0;
    int k;
    int a;
    if(l==0 || w==0 || h==0)
        return ;

    k = min({l, w, h});
    c_idx = log2(k);
    
    for(int i=c_idx; i>=0; i--){
        if( cube[i]>0){
            c_idx = i;
            flag = 1;
            break;
        }
        
    }
   
    if(flag == 0){
        printf("-1\n");
        exit(0);

    }
    
    a=pow(2, c_idx);
    cnt++;
    cube[c_idx]--;
    sol(l-a, w, h, c_idx);
    sol(a, w, h-a, c_idx);
    sol(a, w- a, a, c_idx);

}

int main(void){
    int l, w, h;
    int n;
    int a, b;
    
    scanf("%d %d %d", &l, &w, &h);
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d %d", &a, &b);
        cube[a] = b;
        
    }
    
    sol(l, w, h, n-1);
    printf("%lld\n", cnt);
}