[BOJ] 1493번 : 박스 채우기

문제 링크 : 백준 1493번

[문제 접근]

처음에는 부피로 접근하여 문제를 해결하려고 했지만, 채운 상태인 부피의 모양이 사각형모양이 아닐 수 있기 때문에 부피로는 풀지 못한다는 것을 알았다.

2 3 3
2
0 10
1 10

예를 들어 문제의 입력이 위와같이 주어졌을 때, 박스의 크기는 2x3x3 = 18에 해당한다. 2x2x2 큐브를 2개 담으려면 총 16공간만 있으면 담을 수 있다고 생각했는데 width와 height때문에 2x2x2 큐브를 1개만 담을 수 있다는 것을 알 수 있다.

부피로 접근하여 푼 코드(틀린 코드)

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

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first>b.first;
}

int main() {
    int len, wid, hei;
    cin >> len >> wid >> hei;
    int n;
    cin >> n;
    vector<pair<int, int>> arr;
    for(int i=0 ; i<n ; i++) {
        int a,b;
        cin >> a >> b;
        arr.push_back(make_pair(a,b));
    }
    sort(arr.begin(), arr.end(), cmp);
    long long maxnum = wid*len*hei;
    int ans=0;
    for(int i=0 ; i<n ; i++) {
        long long target = pow(2, arr[i].first);
        if(pow(target,3)*arr[i].second <= maxnum) {
            maxnum -= pow(target,3)*arr[i].second;
            ans += arr[i].second;
        }
        else {
            int index = maxnum/pow(target,3);
            ans += index;
            maxnum -= pow(target,3)*index;
        }
    }
    if(ans == 0) cout << -1;
    else cout << ans;
}

블로그에 있는 코드를 참고해서 해결했다.

[소스코드]

박스 자체를 2^n x 2^n x 2^n으로 분할해 보면서 가지고 있는 큐브를 집어 넣어보는 것(정답 코드)

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

int main() {
    int len, wid, hei;
    cin >> len >> wid >> hei;
    int n;
    cin >> n;
    vector<pair<int, int>> arr;
    for(int i=0 ; i<n ; i++) {
        int a,b;
        cin >> a >> b;
        arr.push_back(make_pair(a,b));
    }

    long long ans=0;
    long long before=0;
    for(int i=n-1 ; i>=0 ; i--) {
        before <<= 3; // before의 개수를 2^3만큼 늘려준다.
        long long pc = (long long) (len >> i) * (wid >> i) * (hei >> i) - before;
        // 박스를 2^i x 2^i x 2^i만큼 분할해 주고, 전에 박스를 채웠던 큐브의 개수(before)만큼 빼 준다.
        // ex) 4 x 4 x 8이기때문에 4 x 4 x 4로 분할하면 1 x 1 x 2 = 2개가 됨
       
        long long nc = min((long long) arr[i].second, pc);
       
        before += nc;
        ans += nc;
    }
    
    if(before == (long long) len * wid * hei) cout << ans;
    else cout << -1;
}