개요

[링크]백준 1493: 박스 채우기

입력
첫째 줄에 세 자연수 length width height가 주어진다.

둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.

셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.

출력
첫째 줄에 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.

접근 방식

• 첫 번째 방식은
  큐브를 하나 채운 후, 나머지 빈 공간을 세 개의 직육면체로
  나누고 재귀함수를 이용해 각각의 직육면체에 또 하나씩 채우는 방법이다.

• 두 번째 방식은
  [링크] 백준 1493 질문글
  이 글을 보고 공부한 것이다.

  입력받은 큐브 중 가장 긴변을 가진 큐브부터 상자에
  최대 몇개 들어갈 수 있는지를 w변수에 저장한다.

  그 다음으로 긴 변을 가진 큐브를 또 상자에 몇개 들어갈 수있는지 비교해야 한다.

  이 과정에서, 바로 전 길이의 큐브가 몇개 들어가 있는지를 보고 남은 공간에 몇개 들어갈수있는질 알아야 한다.

  이 부분은 반복문의 i값이 19에서 줄어들 때마다
  w변수에 2^3을 곱해주면서 비교할 수 있는데,

  예를 들어 큐브 변의 길이가 1과 2가 들어왔을때 과정을 적어보자면

• cubesize가 예를들어 0 1 이렇게 숫자가 들어오면
  처음 w=0이고, 변 길이 2인 큐브가 들어갈 갯수를 저장

  편의상 변 길이 1인 큐브를 1큐브 ,
  변 길이 2인 큐브를 2큐브라고 하자..

• 그 다음 1큐브가 들어온다.
  1큐브입장에서 생각하면
  2큐브가 상자를 차지하고 있는 부분은
  2가 최대로 들어온 갯수에서
  (2 x 2 x 2)인 8을 곱해보면 나온다.

  더 풀어서 얘기하면 2가 최대로 상자를 채운 갯수에
  8을 곱하면 2큐브가 차지한 공간을
  1큐브로 채워넣었을 때 갯수가 나온다.

• 그래서 그 두개를 빼면 2가 차지한 부분을 제외한 부분에
  1로 가득채운 갯수가 나온다.
  이 값과 1큐브 갯수를 비교해서 더 작은 값이
  1큐브가 들어갈 수 있는 최대 갯수이다.

코드

• 첫번째 방식

#include<iostream>															//3
																			
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

vector<pair<int,int>> v;
int ans = 0,fail=0;

void input(int& length,int& width, int& height){
     int cnt=0,cube=0,amountCube=0;
	cin >> length >> width >> height;
	cin >> amountCube;
	for (int i = 0; i < amountCube; i++) {
		cin >> cnt >> cube;
		v.push_back(make_pair(pow(2,cnt),cube));
	}
	sort(v.begin(), v.end(),greater<pair<int,int>>());
}

void solution(int length,int width, int height,int idx) {	                        //재귀함수 length, width, height, 몇번째 큐브인지

	if (length == 0 || width == 0 || height == 0)                                       //만약 0이면 return
		return;
	for (int i = idx; i < v.size(); i++){												    

		if (v[i].second != 0 && (length - v[i].first)>=0 && (width - v[i].first)>=0 && (height - v[i].first)>=0) {
			v[i].second--;																//i번째 큐브 갯수 채워넣었으므로 감소
			ans++;																		//답++
			solution(length , width, height-v[i].first,i);                              //남은 빈 공간 세개를 대상으로 채워넣기 
			solution(length, width-v[i].first, v[i].first,i);
			solution(length - v[i].first, v[i].first, v[i].first,i);
			return;
		}
	}
	fail = 1;                                                                            //빠져 나왔다면 해당하는 큐브값이 없다는 뜻이므로 fail체크후 -1출력
}
void print() {
	if (fail) cout << -1;
	else
		cout << ans;
}

int main() {
	int length=0, width = 0 , height = 0;
    input(length, width, height);
	solution(length, width, height,0);
	print();
}

• 두번째 방식

#include<iostream>														//두번째 방법 그냥 타겟 사각형에 몇개의 큐브가 들어가는지 
																			//갯수만 고려하는 방법
#include<algorithm>

using namespace std;

int a[20];

int main() {
	long long w = 0;
	int t, length, width, height, cubeType = 0;
	int cubeSize, cubeAmount, ans = 0;
	cin >> length >> width >> height >> cubeType;
	for (int i = 0; i < cubeType; i++) {
		cin >> cubeSize >> cubeAmount;
		a[cubeSize] += cubeAmount;
	}
	for (int i = 19; i >= 0; i--) {	//cubesize가 예를들어 1 2 이렇게 숫자가 들어오면 w=0이고 2큐브가 들어갈 갯수를 저장, 
									//그다음 1큐브일 때 생각하면 2가 차있는 부분은 1로 치환해보면 (2*2*2)인 8을 곱해야 2짜리가 차지하는 갯수가 나온다, 
									//그래서 그 두개를 빼면 2가 차지한 부분을 제외한 부분에 1로 가득채운 갯수가 나온다 이값과 1큐브갯수를 비교
		w <<= 3;					//이미 공간 차지한 부분 8배하기	()
		t = min((long long)a[i], (long long)(length >> i) * (width >> i) * (height >> i) - w);		//i길이의 큐브를 다쓴것과 , 
																									//2^i길이의 큐브가 타겟큐브에 들어갈수 있는 갯수 - 이미 공간 차지한 부분
		w += t;						//w에 새롭게 공간 차지한부분 넣기
		ans += t;					//총 갯수
	}
	if (w == (long long)length * width * height)
		cout << ans;
	else
		cout << -1;

}

문풀후생

두 번째 방식은 많이 시간을 투자해서 고민을 한 방식이였다.
정말 기발하고 모양에 신경을 안쓰고 저런식으로 8배씩 해주면서 내려가면서 갯수로만 판단한다는게 신기했다.