백준 BOJ 1493 - 박스 채우기

kks227님 그리디 정주행 완료

마지막문제라 그런지 까다로웠음.

 

그리디에 있기보단 얜 분할정복으로 빼야할거같은데 ㅁㄴㅇㄹ

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

1493번: 박스 채우기

암튼 이 문제는 매우 친절하게도 모든 상자가 2^k 꼴이라

큰 상자는 더 작은 상자 8개로 분해될수 있다.

 

그래서 무조건 큰 상자를 많이 넣는게 이득이므로,

최대한 큰 박스를 하나 우겨넣고 남은 입체도형을

7등분해서

k*k*k 정육면체를 포함한 여덟개의 도형으로 나눠 분할정복하면

문제를 해결할 수 있다.

 

풀고나서 풀이 까봤는데 보통 세개로 많이 나누던데

개인적으로 7개가 더 직관적인듯?

근데 7개로 쪼개면 시간복잡도가 타이트해지는지

pow(2,i) 로 k를 계산하면 tle를 받는다.

1<<i 로 바꿔주자.

 

#include <bits/stdc++.h>
using namespace std;

int num[123] = {0};
bool flag = 1;
long long int ans = 0;

int fill(int x, int y, int z){
	if(!(x&&y&&z)) return 0;
	
	for(int i=19; i>=0; i--){
		int k = 1<<i;
		if(num[i] && x>=k && y>=k && z>=k){
			num[i]--;
			ans++;
			fill(x-k,k,k);
			fill(k,y-k,k);
			fill(k,k,z-k);
			fill(x-k,y-k,k);
			fill(k,y-k,z-k);
			fill(x-k,k,z-k);
			fill(x-k,y-k,z-k);
			return 0;
		}
	}
	flag = false;
	return 0;
}

int main(){
	int x,y,z,n,a,b;
	cin >> x >> y >> z;
	cin >> n;
	
	for(int i=0; i<n; i++){
		cin >> a >> b;
		num[a] = b;
	}
	
	fill(x,y,z);
	
	if(!flag) cout << -1;
	else      cout << ans;
	
	return 0;
}