[백준 C++] 1997 박스포장

문제

동호는 어떤 도자기 장식 판을 포장하는 회사에서 일을 하고 있다. 모든 장식 판은 두께가 1이고 너비가 모두 같으며 각자 자신의 고유한 모양을 가지고 있다.

박스의 너비는 장식 판의 너비와 같아 장식 판을 포장할 때, 차례로 쌓을 수밖에 없다. 예를 들어 위의 장식 판을 차례로 쌓으면 아래의 왼쪽 그림과 같은 모양이 나오게 되고 세 번째 -> 두 번째 -> 첫 번째 순서로 쌓으면 오른쪽 그림과 같이 나오게 된다.

그런데 박스의 높이에는 한계가 있어서 왼쪽과 같은 경우에는 박스를 포장할 수 없게 된다. 그렇기 때문에 왼쪽과 같이 포장을 하려면 박스를 두개로 나누어서 첫 번째 박스는 두 번째 장식 판까지 쌓고, 두 번째 박스에 세 번째 장식 판을 넣어 포장을 해야 할 것이다.

우리가 해야 할 일은 다음과 같다. 어떤 장식 판의 개수, 너비, 박스의 높이, 그리고 장식 판들의 모양이 주어져 있다고 가정하자. 이러한 상황에서 주어진 장식 판을 순서대로 쌓을 때, 사용한 각 박스 안에 쌓은 높이를 출력하는 프로그램을 작성하시오. (ex, 위의 예 같은 경우에는 첫 번째 박스에 2번째 장식 판 까지 쌓아 높이가 9가 되고 두 번째 박스에 세 번째 장식 판을 넣어 높이가 6이 된다. 그래서 답은 9 6이 되는 것이다.)

입력

입력은 첫째 줄에 공백으로 구분된 100을 넘지 않는 세 자연수 n, w, b가 주어진다. n은 장식 판의 종류이고, w는 장식판과 박스의 너비, 그리고 b는 박스의 높이이다. 그리고 다음으로 n개의 장식 판의 정보가 주어지는데, 각 정보의 첫줄에는 장식 판의 높이 h(1 ≤ h ≤ 10, h ≤ b) 가 주어지고 두 번째 줄부터 h+1번째 줄까지 장식 판의 정보가 .과 X로 주어진다. .은 빈 공간을 의미하고 X는 장식 판의 한 부분을 의미한다.

출력

필요한 박스의 개수만큼의 정수를 출력하는데 각 박스에 쌓인 장식 판의 높이를 공백을 사이에 두고 출력한다.

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

풀이

입력으로 주어지는 블럭을 상하 반전시켜서 받는다.
실제 좌표계는 좌상단이 0,0 이나, 블럭을 상자에 쌓는행위는
머릿속으로 구상할때 좌하단을 0,0 으로 생각하고 코드를 짰기 때문이다.

블럭 최대높이가 10이므로 박스를 (b+10,w) 크기로 구현해서,
매번 블럭을 쌓을때마다 쌓은최대높이 + 1을 기억하여 이위치에
블럭을 쌓도록 코드를 짰다.
매번 블럭을 쌓을 수 있는지 확인하는 isRight함수를 통해
블럭을 쌓는 최소높이를 구한뒤, 박스배열에 블럭인위치('X')를 복사했다.

그냥 직관적으로 빡구현을했기때문에 큰 설명은없다...

눈여겨볼점은, 너비는 고정이므로, 너비 W의 한칸한칸의 최대높이를 고려하면? 쉬운코드를 짤 수 있긴할것같다.

사용된 변수/함수 들은 아래와같다.

1. 전역변수

• n, w, b : 입력값
• blocks[N][W][B] : 입력받은 N번째 블럭 모양새
• box[][] : 블럭을 쌓고있는 박스
• box_h : 박스에서 다음블럭이 쌓일 최하단위치(현재 박스최대높이 정수값과동일)
• heighst : blocks와 n을 공유하는, n번째블럭의 높이h들을 저장
• res : 박스가 여럿필요할경우, 각각의 높이를 저장(출력값)
  
  

2. func() : 프로그램의 핵심 로직

• start_h 현재블럭 k를 쌓을 수 있는 최 하단위치
• current_h 현재블럭 k의 높이h

3. isRight() : 박스와 k블럭을 비교하며, 겹치는지 확인. 겹칠경우 false 리턴

4. packing() : 실제로 박스에 k블럭 을 쌓는. 복사하는 함수

5. clear() : 새로 박스를 포장하기위해 박스를 초기화하는 함수

6. printAll() : res의 내용을 모두출력. 정답출력

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector;
int n, w, b, ***blocks, **box, box_h=0;
vector<int> heights, res; 
void clear();
void func();
bool isRight(int block_num, int start_h);
void packing(int block_num, int start_h);
void printAll();

//정답출력
void printAll() {
	for (int i = 0; i < res.size(); i++)
		printf("%d ", res[i]);
}

//박스 초기화
void clear() { 
	for (int i = 0; i < b + 10; i++)
		for (int j = 0; j < w; j++)
			box[i][j] = 0;
}

void func() {
	box = new int* [b + 10]; 
	for (int i = 0; i < b + 10; i++)
		box[i] = new int[w];

	clear(); //처음 초기화
	
	for (int k = 0; k < n; k++) {
		int start_h; //블럭을 놓을수있는 최소 높이
		int current_h = heights[k]; //현재블럭의 높이

		for (start_h = box_h +1; start_h > 0; start_h--) { //pack의 현재 최대높이 + 1 부터 확인
			if (!isRight(k, start_h)) { //불가능하면 끝
				break;
			}
		}
		if(box_h != 0) //이미 블럭이 쌓여있던경우 그 위칸부터 블럭을 쌓기시작
			start_h++; 

		if (start_h + current_h > b) { //1.쌓고난뒤 높이가 박스를 초과한경우
			res.push_back(box_h); //현재 박스최대 높이(인덱스X) 결과로 저장
			clear(); //박스 리셋
			box_h = current_h;  //현재 박스최대높이(인덱스X)를 현재블럭높이로 갱신
			packing(k, 0); //박스바닥부터 블럭을 쌓음
		}
		else if (start_h + current_h == b) { //2.쌓고난뒤 높이가 박스와 일치
			res.push_back(b); //박스높이를 결과로 저장
			clear(); //박스 리셋
			box_h = 0; //박스 최대높이 0으로 갱신
		}
		else { //3.쌓은높이가 아직 박스보다 작을때
			packing(k, start_h); //실제로 블럭을 쌓음
			box_h = start_h + current_h; //박스 최대높이 갱신
		}

		//마지막에 박스에 쌓은블럭이남았으면 결과로 저장
		if (k == n - 1 && box_h != 0)  
			res.push_back(box_h);
	}

}

//블럭을 놓을수 있는지 확인
bool isRight(int block_num, int start_h) { 
	int h = heights[block_num];
	for (int i = start_h; i < start_h + h; i++) { //블럭이 안겹치는지 확인
		for (int j = 0; j < w; j++) {
			//박스와 블럭이 겹치면 안됨
			if (box[i][j] == 1 && blocks[block_num][i - start_h][j] == 1)
				return false; //놓을 수 없음
		}
	}
	return true;
}

//박스에 블럭을 쌓음
void packing(int block_num, int start_h) { 
	int h = heights[block_num];
	for (int i = start_h; i < start_h + h; i++) { 
		for (int j = 0; j < w; j++) {
			if(blocks[block_num][i - start_h][j] == 1) //블럭인부분만
				box[i][j] = 1;
		}
	}
}

int main(void) {
	scanf("%d%d%d", &n, &w, &b);
	blocks = new int** [n]; //blocks 블럭형태
	for (int k = 0, h; k < n; k++) {
		scanf("%d", &h);
		heights.push_back(h);
		blocks[k] = new int* [h];
		char c;
		//블럭이 아래부터쌓으나, 실제 메모리상에는 아래에서 위로 쌓이므로
		//입력을 상하반전으로 받음.
		for (int i = h - 1; i >= 0; i--) { 
			blocks[k][i] = new int[w];
			scanf("%c", &c); //줄바꿈문자지움
			for (int j = 0; j < w; j++) {
				scanf("%c", &c); //블럭읽어옴
				if (c == 'X')
					blocks[k][i][j] = 1; //블럭
				else
					blocks[k][i][j] = 0; //공란
			}
		}

	}
	func();
	printAll();

	return 0;
}