박스 채우기 1493

1. 기본 설명

분할과 정복에서 가장 정직한? 이름에 걸맞는 유형

내가 푼 방법은 들어갈 수 있는 박스를 하나 집어넣고 남는 공간을 3등분 하여 다시 각각의 공간에 대해 들어갈 수 있는 제일 큰것을 집어넣는 재귀 방식으로 풀었다.

코드를 한번 봐 보자

#include <iostream>
#include <vector>
#include<algorithm>
#include<cmath>
using namespace std;

int l, w, h,n;
int minV;
long long _count = 0;
bool suc;
vector<pair<int,int>> v;
//현재 공간에 정육면체가 들어갈수 있는지 체크
bool checkSize(int length, int width, int height, int x) {
    if (length < x || width < x || height < x) {
        return false;
    }
    return true;
}

//가장 적게 들어가는 경우를 탐색
void findMin(int x, int y, int z) {
    
    if (x <= 0 || y <= 0 || z <= 0) {
        return;
    }

    minV = min({ x, y, z });
    int curPos = -1;
    for ( curPos = n-1; curPos >= 0; curPos--) {
        if (v[curPos].second > 0) {
            if (checkSize(x,y,z,v[curPos].first)) {
                break;
            }
        }
    }
    if (curPos == -1) {
        cout << "-1" << endl;
        exit(0);
    }

    int blockLen = v[curPos].first;
    v[curPos].second -= 1;
    _count++;
    //3부분으로 나눠서 다시 findMin으로 경우 탐색
    findMin(x - blockLen, y, z);
    findMin(blockLen, y, z - blockLen);
    findMin(blockLen, y - blockLen, blockLen);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> l >> w >> h;
    cin >> n;
    int tmp1,tmp2;
    for (int i = 0; i < n; i++) {
        cin >> tmp1 >> tmp2;        
        v.push_back(pair<int,int>(pow(2,tmp1),tmp2));
    }

    findMin(l, w, h);

    cout << _count <<endl;
    
    return 0;
}

2. 작동 원리

• 그림판으로 그려서 별로지만 대충 저런식으로 왼쪽 아래 빨간색이 이번에 둔 가장 큰 정육면체라 할때, 나머지 부분을 3부분으로 나눠서(divide) 채워넣어 간다(conquer)
• 더욱 자세한 내용은 주석과 코드를 참고하면 되겠다.

3. 배운 점

• 이번에도 또또또!!! 출력에서 실수해서 몇번 실패가 떴다. 항상 출력부분을 잘 생각하자
• 함수 호출을 여러번하는게 별로 맘에 안들어서 최대한 호출을 적게하려고 했지만... 능력이 안되더라.. 재귀가 참 편하긴하다. 스택프레임 다시 푸는게 시간좀 걸릴거 같다고 생각했는데 생각보다 빠르다.
• 제에에에에발 타입 신경쓰자. 최악의 경우를 생각해서 출력을 맡을 변수의 타입을 정하자. 이 문제도 가로, 세로, 높이 10만씩 가능하니까 부피가 최대 1경까지 간다. 무지성 int는 하지 말자.