C++[백준]1493번 박스 채우기

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

1493번: 박스 채우기

오랜만에 포스팅..

 

 

솔루션

---

처음에 정육면체 자르기와 비슷하다 생각하여 DP로 생각해 보았지만, 입력 값이 10^6이라고 해서 dp 배열을 잡기에는 무리가 있다.

 

그래서 나는 그리디로 한 번 도전 해 보았는데, 다행이게도 맞았습니다를 받았다.

 

먼저 가장 큰 큐브부터 박스에 넣을 수 있다면, 박스에 넣어주고 남는 공간을 재귀로 호출한다.

만약 박스에 큐브를 채워 넣으면 남는 공간은

l, w, h - CubeSize //채워 놓은 뒤, 위쪽 공간

l - CubeSize, CubeSize, CubeSize //채워 놓고, 높이를 자르고 남는 박스의 앞쪽 공간

l, w-CubeSize, CubeSize //채워놓은 뒤, 박스의 남은 폭 공간.

 

이렇게 세 개를 호출하면 된다.

해당하는 사이즈의 큐브 개수가 없거나, 너비나 폭 높이가 큐브 사이즈보다 작으면 더 작은 큐브로 바꿔서 재귀를 계속해서 호출하면 된다.

 

코드

---

#include <iostream>
#include <vector>
using namespace std;
struct pa {
	int size, num;
};

int L, W, H;
vector<pa>V;
int N;

int cnt = 0;
int solve(int l, int w, int h, int idx) {
	if (idx == -1) {
		return -1;
	}
	if (l == 0 || w == 0 || h == 0) return 0;
	int cur = 1 << V[idx].size;
	int dest = min(l, min(w, h));

	if (cur > dest || V[idx].num == 0) {
		return solve(l, w, h, idx - 1);
	}
	else { 
		int ref = 0;
		V[idx].num--;
		cnt++;
		ref = min(solve(l, w, h - cur, idx), ref); //높이 쪽으로 남는 공간
		ref = min(solve(l - cur, cur, cur, idx),ref); //박스의 lengh 쪽으로 남는 공간
		ref = min(solve(l, w - cur, cur, idx),ref); //박스의 폭으로 남는공간
		return ref;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> L >> W >> H;
	cin >> N;

	for (int i = 0; i < N; i++) {
		pa t;
		cin >> t.size >> t.num;
		V.push_back(t);
	}
	solve(L, W, H, V.size() - 1) == -1 ? cnt = -1 : cnt = cnt;
	cout << cnt << '\n';
}