1770. [SW Test 샘플문제] 블록 부품 맞추기

문제: https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

 

문제 풀이:

우리는 header와 main 함수 부분을 제외한 부분을 라이브러리를 사용하지 않고 채우면 된다.

main 코드를 보면 한 블록에서 높이는 다음과 같이 나올 수 있다.

base는 1~6까지가 나올 수 있고, 거기에 플러스로 0~2가 더해진 수가 나올 수 있으므로 높이는 1~8가 나올 수 있다.

 

높이가 최대 8밖에 안되므로 long long형 16자리로 표현할 수 있다.

1	1	1	1
2	2	2	2
3	3	3	3
4	4	4	4

=> 1111222233334444 이런식으로

 

블록의 모양을 state라고 하자.

 

hash_table을 만들어 각 블록의 state를 저장하였다.

 

1. 블록 하나를 고른다

2. 블록을 뒤집는다. (둘 중 하나는 뒤집어서 맞대어야하므로)

3. 뒤집은 블록을 0, 90, 180, 270도로 회전한 것을 long long 형태로 저장한다.

4. 임의로 고른 블록과 서로 맞대어 육면체를 만들 수 있는 블록은 다음과 같은 모양을 가져야한다.

 

한 블록(A)이 정해졌을 때, 두 블록을 합쳐서 나올 수 높이는

최소: [A에서의 최대값 +1]

최대: [A에서의 최소값 + 8]  

 

우리는 두 블록을 합쳤을 때 최대가 되도록 하고 싶으므로 최대인 것부터 한 층씩 깎아서 해당 블록이 해시 테이블에 존재하는지 확인한다.

 

 

 

즉,

1. 고른 블록의 각 0˚, 90˚, 180˚, 270˚ 상태와 맞댈 수 있는 최대 높이의 블록이 해시 테이블에 존재하는지 확인
2. 없다면 최대 높이-1로 깎음(현재 찾고자 하는 블록-111111111111111)
3. 가능한 블록의 최소값까지 반복
4. 만약 가능한 블록을 찾았다면 
   1. 그 블록이 자신과 같은지 확인 (자기 자신과 합쳐질 수도 있으므로)
   2. 아니라면 sum+=두 블록의 합, 두 블록은 이제 사용 불가하므로 해시 테이블에서 지움

 

 

실행 시간: 487ms

 

 

소스 코드:

#include <iostream>
#include <stdlib.h>

#define MAX 30000

#define a 17
#define b 7
#define HASHSIZE 100019


#define one 1111111111111111

typedef long long ll;
ll hash_table[100019], cur[4];
int turn[2][16];
int sum;
using namespace std;

struct block {
	int maxH;
	int minH;
	ll state;
};
block bl[MAX + 1];

void init() {

	for (int i = 0; i < HASHSIZE; i++) {
		hash_table[i] = -1;
	}
	sum = 0;
}
void insert(ll key) {
	int p = (a*key - b) % HASHSIZE;
	while (hash_table[p] != -1) {
		p = (p + 1) % HASHSIZE; 
	}
	hash_table[p] = key;
}
int find(ll key) {
	int p = (a*key - b) % HASHSIZE;
	int first = p;

	while (hash_table[p] != key) {
		if (hash_table[p] == -1) return -1; // 없음
		p = (p + 1) % HASHSIZE;
	}
	return p;
}
ll returnstate(int p) {
	ll tmp = 0;
	for (int i = 0; i < 16; i++) {
		tmp = tmp * 10 + turn[p][i];
	}
	return tmp;
}
void findpair(ll state, int maxH) {
	int tmp[16]; // 현재 블록과 성립할 수 있는 가장 높은 블럭
	for (int i = 0; i < 16; i++) {
		tmp[15 - i] = maxH - (state % 10);
		state /= 10;
	}

	int t = 12;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			turn[0][t + j] = tmp[i * 4 + j];
		}
		t -= 4;
	}
	cur[0] = returnstate(0);

	//turn
	for (int c = 1; c < 4; c++) {
		int p = 0;
		for (int i = 12; i <= 15; i++) {
			int tt = i;
			while (tt >= 0) {
				turn[c % 2][p] = turn[(c + 1) % 2][tt];
				tt -= 4;
				p++;
			}
		}
		cur[c] = returnstate(c % 2);
	}
}
extern int makeBlock(int module[][4][4]);


// 최대 높이(int), 최소 높이(int), 상태(ll)
int makeBlock(int module[][4][4]) {
	init();
	for (int i = 0; i < MAX; i++) {
		ll t = 0;
		int maxH = 0;
		int minH = 10;
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				int m = module[i][j][k];
				t = t * 10 + m;
				maxH = maxH < m ? m : maxH;
				minH = minH > m ? m : minH;
			}
		}
		insert(t);
		bl[i].minH = minH;
		bl[i].maxH = maxH;
		bl[i].state = t;
	}
	for (int i = 0; i < MAX; i++) {
		// 이미 사용한 블록이면 패스
		int v = find(bl[i].state);
		if (v==-1) continue;


		findpair(bl[i].state, bl[i].minH + 8);

		for (int j = bl[i].minH + 8; j >= bl[i].maxH + 1; j--) {
			bool f = false;
			for (int k = 0; k < 4; k++) {
				int p = find(cur[k]);
				if (p != -1 && cur[k] != bl[i].state) {
					hash_table[p] = -1;
					p = find(bl[i].state);
					hash_table[p] = -1;

					sum += j;
					f = true;
					break;
				}
				cur[k] -= one;
			}
			if (f) break;
		}
	}
	return sum;
}
int main(void)
{
	static int module[MAX][4][4];

	srand(3); // 3 will be changed

	for (int tc = 1; tc <= 10; tc++)
	{
		for (int c = 0; c < MAX; c++)
		{
			int base = 1 + (rand() % 6);
			for (int y = 0; y < 4; y++)
			{
				for (int x = 0; x < 4; x++)
				{
					module[c][y][x] = base + (rand() % 3);
				}
			}
		}
		cout << "#" << tc << " " << makeBlock(module) << endl;
	}

	return 0;
}