글 읽기 - 재귀를 재귀재귀

kyma123 9년 전 0

심심해서 좀 어려워 보이는 문제에 한 번 손을 대 봤는데, 규칙은 생각보다 어렵지 않아서 알고리즘 쌩까고 모든 테스트 케이스 점검하는 재귀로 짜 봤습니다.

근데 문제는 구슬의 추가가 많을 경우, 최대 4 * 12! 까지 발생할 수 있는 경우의 수를 감당 못한다는 것(..)

이동이 구슬 추가보다 많은 경우에는 메모리도 별로 안 잡아먹고 잘 돌아가는데, 구슬 추가로 도배를 해 뒀을 경우에는 제한시간 5초도 가뿐히 넘기더라고요 으윽

제출해 봤더니 75%까진 채점 되다가 마지막에 역시나 시간 초과.

일단 제가 짠 발코드는 아래에 있고요, 재귀 횟수를 최소화 하는 방법 없을까요... 최종 결과에서 역으로 Action해서 각 좌표마다 해당 구슬이 있을 확률을 저장하는 방식도 생각은 해 봤는데 규칙을 세우기가 상당히 복잡하더라고요.

그나저나 제 코드 다시 보니 심히 더럽군요 으악ㅋㅋㅋ

operator+로 구슬 추가를 하려다보니 우항에 정수를 압축해서 넣을 수 밖에 없었습니다ㅋㅋㅋㅋㅋㅠㅠㅠ

#include <iostream>
using namespace std;

// W - 1, G - 2, E - 0
class board {
public:
	int arr[4][4];
	board() {
		for (int i = 0; i < 16; i++)
			*(arr[0] + i) = 0;
	}
	board(const board& o) {
		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 4; j++)
				arr[i][j] = o.arr[i][j];
	}
	board& operator=(const board& o) {
		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 4; j++)
				arr[i][j] = o.arr[i][j];
		return *this;
	}
	void tilt(int c) {
		int k;
		if (c == 0) {
			for (int i = 1; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					k = i;
					while (k > 0 && arr[k][j] > 0 && arr[k - 1][j] == 0) {
						arr[k - 1][j] = arr[k][j];
						arr[k--][j] = 0;
					}
				}
			}
		}
		else if (c == 1) {
			for (int i = 2; i >= 0; i--) {
				for (int j = 0; j < 4; j++) {
					k = i;
					while (k < 3 && arr[k][j] > 0 && arr[k + 1][j] == 0) {
						arr[k + 1][j] = arr[k][j];
						arr[k++][j] = 0;
					}
				}
			}
		}
		else if (c == 2) {
			for (int i = 0; i < 4; i++) {
				for (int j = 1; j < 4; j++) {
					k = j;
					while (k > 0 && arr[i][k] > 0 && arr[i][k - 1] == 0) {
						arr[i][k - 1] = arr[i][k];
						arr[i][k--] = 0;
					}
				}
			}
		}
		else {
			for (int i = 0; i < 4; i++) {
				for (int j = 2; j >= 0; j--) {
					k = j;
					while (k < 3 && arr[i][k] > 0 && arr[i][k + 1] == 0) {
						arr[i][k + 1] = arr[i][k];
						arr[i][k++] = 0;
					}
				}
			}
		}
	}
};
inline bool operator==(const board* l, const board r) {
	int n = 0;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			if (l->arr[i][j] == r.arr[i][j])
				n++;
	return n == 16;
}
// board에 새로운 구슬을 추가해서 그 포인터를 리턴
// r의 100의 자리: 구슬의 종류, 10의 자리: row, 1의 자리: col
inline board* operator+(const board l, const int r) {
	board* b = new board();
	*b = l;
	b->arr[r / 10 % 10][r % 10] = r / 100;
	return b;
}

board answer;
int cases, total;

void func(int m, char* action, board* b) {
	if (m == 0) {
		total++;
		if (b == answer)
			cases++;
		if (b) { delete b; b = NULL; }
		return;
	}
	int k = 0; // k : 구슬의 종류 저장, W - 1, G - 2
	int t = 0; // t : 중앙에 구슬이 있는 좌표를 합으로 저장(i: 10의 자리, j: 1의 자리)
	switch (*action) {
	case 'G':k++;
	case 'W':k++;
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= 2; j++) {
				if (b->arr[i][j] > 0)
					t += 10 * i + j;
			}
		}
		if (0 < t && t < 23) { // 구슬이 한 개만 있는 경우
			func(m - 1, action + 1, *b + (100 * k + 33 - t));
		}
		else if (t < 44) { // 구슬이 없거나 두 개가 있는 경우
			for (int i = 1; i <= 2; i++) {
				for (int j = 1; j <= 2; j++) {
					if (b->arr[i][j] == 0)
						func(m - 1, action + 1, *b + (100 * k + 10 * i + j));
				}
			}
		}
		else if (t < 66) { // 구슬이 세 개가 있는 경우
			func(m - 1, action + 1, *b + (100 * k + 66 - t));
		}
		else { // 중앙 부분이 가득 찬 경우
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					if (b->arr[i][j] == 0)
						func(m - 1, action + 1, *b + (100 * k + 10 * i + j));
				}
			}
		}
		break;
	// make T - 0, B - 1, L - 2, R - 3
	default: b->tilt(*action % 7 * 3 % 4); func(m - 1, action + 1, new board(*b));
	}
	if (b) { delete b; b = NULL; }
}

void input() {
	char c;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++) {
			cin >> c;
			answer.arr[i][j] = (c - 'E') ? (c - 'W') ? 2 : 1 : 0;
		}
}
int main() {
	int n, m;
	char* action;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cases = total = 0;
		cin >> m;
		action = new char[m];
		for (int j = 0; j < m; j++)
			cin >> action[j];
		input();
		func(m, action, new board);
		cout << (float)cases / total << endl;
		delete[] action;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

재귀를 재귀재귀

kyma123 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말