2 Problem F : 합이 0이 되는 4개의 숫자들

숫자를 원소로 가지고 있는 A, B, C, D 집합이 있음

a + b + c + d = 0 인 경우의 수가 몇 가지인가 계산하는 프로그램을 작성하라

집합의 크기가 4,000 가능하므로 완전 탐색의 경우 (4,000)^4 시간 초과 발생

따라서 4,000^2 으로 두 부분 집합으로 만들고, radix sort 후 sliding window 로

시간을 줄일 수 있다

 

#include <stdio.h>
//#define tet_MAX 30010
#define tet_MAX 31
int N, M, H, P, tet[tet_MAX], gogo[3]; // 테트의 위치를 비트로 표현함

void rotate(int b[3][3])
{
	int a[3][3], i, j;
	for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) { // 회전 시키고
		a[i][j] = b[j][2 - i];
	}
	for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) { // 그것을 입력함
		b[i][j] = a[i][j];
	}
}

void input()
{
	int block[3][3], R, S, i, j; // 들어온 블럭, 회전, 이동
	for (i = 2; i >= 0; i--) for (j = 0; j < 3; j++) scanf("%d", &block[i][j]); // 왜 i를 2부터 받지?
	scanf("%d %d", &R, &S); // 회전수와 이동수
	R %= 4; // 4회전 하면 동일하므로
	if (S > N) S = N; // 이동 수가 행보다 크면 S = N 으로 입력
	while (R--) rotate(block); // 회전 함 블럭을
	//3x3을 3x1로 압축함
	for (i = 0; i < 3; i++) gogo[i] = (block[i][2] << 2) + (block[i][1] << 1) + block[i][0]; // 테트 비트 표현
	// 왼쪽이 비었으면 왼쪽으로 이동함
	while ((gogo[0] & 1) + (gogo[1] & 1) + (gogo[2] & 1) == 0) for (i = 0; i < 3; i++) gogo[i] >>= 1;
	// 제일 아래칸이 비었으면 아래로 이동 시킴
	while (gogo[0] == 0) gogo[0] = gogo[1], gogo[1] = gogo[2], gogo[2] = 0;
	// S만큼 이동시킴
	for (i = 0; i < 3; i++) gogo[i] <<= S;
	// 오른쪽으로 넘어갔으면 안쪽으로 한칸 당김
	while (gogo[0] > P || gogo[1] > P || gogo[2] > P) for (i = 0; i < 3; i++) gogo[i] >>= 1;
}

void drop()
{
	int i, j, k;

	for (i = H; i > 0; i--) {
		if ((tet[i] & gogo[0]) + (tet[i + 1] & gogo[1]) + (tet[i + 2] & gogo[2])) break;
	}

	for (++i, j = 0; j < 3; i++, j++) {
		tet[i] += gogo[j];
		if (tet[i] && i > H) H = i; // 가장 높은 곳의 위치
	}
	for (j = i - 1; j >= i - 3; j--) { // 위에서부터 검사해서
		if (tet[j] == P) { // 그 행이 모두 찼으면
			for (k = j; k <= H; k++) tet[k] = tet[k + 1];
			H--;
		}
	}
}

int main()
{
	scanf("%d %d", &N, &M); // 행, 들어오는 블럭 숫자
	P = (1 << N) - 1; // 행이 가득 찼을 때 체크하는 변수
	while (M--) { // 블록을 넣고, 쌓기
		input();
		drop();
	}
	printf("%d\n", H);
	return 0;
}