[백준] 1493-박스채우기(C++)

문제링크: https://www.acmicpc.net/problem/1493

1493번: 박스 채우기

 

정렬을 하고 최선의 선택을 함으로써 결과를 도출하는 그리디 문제입니다.

 

처음에는 부피로 접근하여 문제를 해결하려고 했지만, 부피가 크다고 해당 범위를 채울 수 없는 것을 깨닭았습니다.

왜냐하면 한번 채운 상태인 부피의 모양이 사각형모양이 아닐 수 있기 때문입니다. 

 

문제해결하기위해서는 

분할정복 개념에 대해서 아셔야합니다.

 

저는 가장큰 박스로 채우고 나머지 부분을 재귀호출을 통해서 결과를 얻게끔 하였습니다. 

 

코드를 이해하시고 꼭 직접 작성해보세요.

 

정답코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
struct var{
	int a;
	int b;
};
bool cmp(var t1, var t2) {
	if (t1.a > t2.a) return true;
	return false;
}
int l, w, h, n;
int result = 0;
var arr[20];
bool jud = true;
void solved(int ll, int ww, int hh) {
	if (jud == false) return;
	if (ll == 0 || ww == 0 || hh == 0) return;

	for (int i = 0; i < n; i++) {
		if (ll >= arr[i].a && ww >= arr[i].a && hh >= arr[i].a && arr[i].b > 0) {
			arr[i].b--;
			result++;
			solved(ll, ww, hh - arr[i].a);
			solved(arr[i].a, ww - arr[i].a, arr[i].a);
			solved(ll - arr[i].a, ww , arr[i].a);
			return;
		}
	}

	jud = false;
}


int main() {
	cin >> l >> w >> h;
	cin >> n;
	int temp1, temp2;
	for (int i = 0; i < n; i++) {
		cin >> temp1 >> arr[i].b;
		arr[i].a = pow(2,temp1);
	}
	sort(arr, arr + n, cmp); // 내림차순 정렬

	solved(l, w, h);

	if (jud == false)
		cout << -1 << endl;
	else
		cout << result << endl;
}