Problem D : 쌓기나무

 

제한시간: 2000 ms    메모리제한: 64 MB

 

 

경수네 반은 실과시간에 쌓기나무 놀이를 하였다.

맨 아랫면은 4 * 4의 모양을 모두 채워놓고 그 위에는 각 위치마다 다른 높이로 쌓아서 접착제로 붙여 놓았다.

 

 

수업시간이 끝나고 나니 각자 만들어 놓은 쌓기나무가 제각각 널부러져 있었다.
경수는 각 쌓기나무 위에 다른 쌓기나무를 엎어서 꼭 맞는 것들을 찾아서 이어서 최대한 높이 쌓아보기로 했다.

예를 들어 두 개의 쌓기나무의 위치별 높이가 아래와 같다고 하자.

 

오른쪽 쌓기나무를 뒤집어서 왼쪽 쌓기나무 위에 놓으면 빈틈없이 높이가 5인 직육면체가 된다.

 

밑면이 4 * 4인 N개의 쌓기나무가 주어질 때 위와 같이 빈틈없이 채워서 쌓을 수 있는 쌍들을 이어서 최대 높이를 구하는 프로그램을 작성하시오.

 

입력과 출력은 메인함수에서 실행되므로 사용자는 makeTree() 함수만 작성해서 결과값만 리턴하면 된다.

makeTree() 함수에서는 scanf, printf, cin, cout과 같은 입출력 함수를 사용해서는 안된다.

아래에 주어지는 main() 함수는 채점시 자동으로 포함되므로 참고만 하고

채점시에는 makeTree() 함수를 포함하여 자신이 작성한 소스만 제출하면 된다.

 

//=== user code : template ===
int makeTree(int module[][4][4])
{
    int ans = 0;
 
    // implement here
 
    return ans;
}
 
 
//=== main code : template ===
#include <iostream>
#include <stdlib.h>
#define N 30000
using namespace std;
 
extern int makeTree(int tree[][4][4]);
 
int main(void)
{
    static int tree[N][4][4];
 
    srand(5);
 
    for (int tc = 1; tc <= 20; tc++)
    {
        for (int c = 0; c < N; c++)
        {
            int base = 1 + (rand() % 6);
            for (int y = 0; y < 4; y++)
            {
                for (int x = 0; x < 4; x++)
                {
                    tree[c][y][x] = base + (rand() % 3);
                }
            }
        }
        cout << "#" << tc << " " << makeTree(tree) << endl;
    }
 
    return 0;
}

 

입력은 20개의 테스트 케이스로 이루어지며 한 개의 테스트 케이스에는 30,000개의 쌓기나무 정보가 자동으로 생성되어 주어진다. 쌓기나무의 밑면은 4 * 4의 배열 형태이며 각각의 높이는 1이상 10이하이고 한 개의 쌓기나무의 최대높이와 최소 높이의 차는 2 이하이다. 자세한 내용은 main 함수를 분석해 보면 된다.

각 테스트 케이스마다 쌓기나무를 빈틈없이 이어서 최대로 쌓았을 때의 높이를 리턴하면 메인에서 자동으로 출력한다.

 

#1 356

#2 406

#3 413

#4 363

#5 390

#6 255

#7 403

#8 546

#9 433

#10 424

#11 342

#12 484

#13 301

#14 441

#15 556

#16 389

#17 367

#18 298

#19 373

#20 474

 

 

※ srand(5) 일 경우의 출력예이며 컴파일러에 따라 결과가 다르게 출력될 수도 있다. 실제 채점시에는 rand() 함수내의 5는 다른 숫자로 변경될 것이다. 위 결과는 운영체제 : 윈도우, VS2013인경우이다.

 

#include <iostream>
#include <stdlib.h>
#define N 30000
using namespace std;

extern int makeTree(int tree[][4][4]);

int main(void)
{
	static int tree[N][4][4];

	srand(5);

	for (int tc = 1; tc <= 20; tc++)
	{
		for (int c = 0; c < N; c++)
		{
			int base = 1 + (rand() % 6);
			for (int y = 0; y < 4; y++)
			{
				for (int x = 0; x < 4; x++)
				{
					tree[c][y][x] = base + (rand() % 3);
				
			}
		}
		cout << "#" << tc << " " << makeTree(tree) << endl;
	}

	return 0;
}

#define LN 30000
#define KEY (a[i].key >> k) & (P - 1)

const int P = (1 << 8);
struct data {
	int id, base, key;
} A[LN], B[LN], C[LN];
int chk[LN], cnt[P];

int Min(int x, int y) { return x < y ? x : y; }
int Max(int x, int y) { return x > y ? x : y; }

void r_sort(data *a, data *b)
{
	int i, k;
	data *t;
	for (i = 0; i <= 10; i++) cnt[i] = 0;
	for (i = 0; i < LN; i++) cnt[a[i].base]++;
	for (i = 9; i >= 0; i--) cnt[i] += cnt[i + 1];
	for (i = LN - 1; i >= 0; i--) b[--cnt[a[i].base]] = a[i];
	for (i = 0; i < LN; i++) a[i] = b[i];

	for (k = 0; k < 32; k += 8) {
		for (i = 0; i < P; i++) cnt[i] = 0;
		for (i = 0; i < LN; i++) cnt[KEY]++;
		for (i = 1; i < P; i++) cnt[i] += cnt[i - 1];
		for (i = LN - 1; i >= 0; i--) b[--cnt[KEY]] = a[i];
		t = a; a = b; b = t;
	}
}

int cal(int m[4][4])
{
	int val[4] = { 0 }, i, j;
	for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) { // 4가지 방향으로 돌렸을 때 계산을 해둠
		val[0] = val[0] * 3 + m[i][j];
		val[1] = val[1] * 3 + m[3 - j][i];
		val[2] = val[2] * 3 + m[3 - i][3 - j];
		val[3] = val[3] * 3 + m[j][3 - i];
	}
	return Min(Min(val[0], val[1]), Min(val[2], val[3])); // 제일 작은 값을 찾아둠. 이건 유일하게 만들기 위해.
}

void make(int id, int m[4][4])
{
	int min = 10, max = 0, i, j, a[4][4], b[4][4];
	A[id].id = B[id].id = id;
	for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) {
		min = Min(min, m[i][j]), max = Max(max, m[i][j]); // 하나의 블록에서 제일 작은 값과 큰 값 찾기
	}
	A[id].base = min, B[id].base = max; // 하나의 블럭에 대해서 2개를 만듬
	for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) {
		a[i][j] = m[i][j] - min; // 베이스를 뺌
		b[i][j] = max - m[i][3 - j]; // 덮개를 만들음
	}
	A[id].key = cal(a), B[id].key = cal(b); // 짝이 맞는지 안맞는지 여기서 확인 가능
}

int makeTree(int module[][4][4])
{
	int ans = 0, i;
	for (i = 0; i < LN; i++) {
		make(i, module[i]);
		chk[i] = 0;
	}
	r_sort(A, C); // 4방향 중 제일 작은 값들을 저장해 둠
	r_sort(B, C);
	int l = 0, r = 0;
	while (l < LN && r < LN) {
		if (chk[A[l].id]) l++; // 사용했으면
		else if (chk[B[r].id]) r++; // 사용했으면
		else if (A[l].id == B[r].id) r++; // 아이디가 같은 경우 오른쪽 전진
		else if (A[l].key < B[r].key) l++;
		else if (A[l].key > B[r].key) r++;
		else {
			ans += A[l].base + B[r].base;
			chk[A[l].id] = chk[B[r].id] = 1;
			l++, r++;
		}
	}
	return ans;
}