1493 박스 채우기

으음... 가장 큰 상자부터 빼는 방식으로 구현하려 했는데 어디 문제가 생긴 것 같다..

 

큐브 개수를 저장하는 cube배열과 길이를 저장하는 two배열을 만든 다음

 

재귀함수를 돌려 l, w, h에 길이를 계속 빼나갔는데 음... 엄... 예시를 넣으면 -1이 나온다.

 

조금 더 생각해봐야 할듯

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int ans = 0;
int cube[25];
int two[25];

bool res = true;

void solve(int l, int w, int h, int i)
{
    if (i == -1)
    {
        if (l > 0 && w > 0 && h > 0)
            res = false;
        
        return;
    }

    if (two[i] > l || two[i] > w || two[i] > h || cube[i] == 0)
    {
        solve(l, w, h, i - 1);
        return;
    }

    cube[i]--;
    ans++;

    solve(l, w - two[i], two[i], i);
    solve(l - two[i], two[i], two[i], i);
    solve(l, w, h - two[i], i);
}

int     main()
{
    int l, w, h;
    scanf("%d %d %d", &l, &w, &h);

    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        cube[a] = b;
    }

    for (int i = 1, j = 0; j < 20; i *= 2, j++)
        two[j] = i;

    solve(l, w, h, 19);

    if (!res)
        printf("-1\n");
    else
        printf("%d\n", ans);

    return 0;
}

 

---

 

오! 3등분 하라는 게 이거였구나!!!

 

대박 이제 알겠다

 

저렇게 자르면 다시 상자가 되니깐 그걸 재귀로 다시 돌리면 되는구나.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int ans = 0;
int cube[25];
int two[25];

bool res = true;

void solve(int l, int w, int h, int i)
{
    if (i == -1)
    {
        if (l > 0 && w > 0 && h > 0)
            res = false;
        
        return;
    }

    if (two[i] > l || two[i] > w || two[i] > h || cube[i] == 0)
    {
        solve(l, w, h, i - 1);
        return;
    }

    cube[i]--;
    ans++;

    solve(l, w - two[i], two[i], i);
    solve(l - two[i], two[i], two[i], i);
    solve(l, w, h - two[i], i);
}

int     main()
{
    int l, w, h;
    scanf("%d %d %d", &l, &w, &h);

    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        cube[a] = b;
    }

    for (int i = 1, j = 0; j < 20; i *= 2, j++)
        two[j] = i;

    solve(l, w, h, 19);

    if (!res)
        printf("-1\n");
    else
        printf("%d\n", ans);

    return 0;
}

 

끝~~ 

 

 

if (i == -1)
    {
        if (l > 0 || w > 0 || h > 0)
            res = false;
        
        return;
    }

 

마지막에 이 부분에서 문제였다.

 

내 생각에는 전부 0이어야 빈 공간이 없을거라 생각하고 저렇게 구현했는데 자꾸 틀렸다.

 

다른 사람 코드 보면 || 대신에 &&를 썼는데 알고보니 길이 중 하나가 0이라면 부피가 0이 되서 그렇다.

 

0*w*h = 0이니깐..