글 읽기 - 시간초과 어떻게 해결하여야 할까요?

zxcv1534 7년 전 1

2048(easy)는 정답을 받았습니다. 하지만 hard는 10번이라 그런지 시간초과가 나는데요. 어떻게 이걸 줄여야할지 감이 안 옵니다. 방향이라도 알려주실 친절한 분 계신가요??

코드는 재귀로 각 방향으로 움직이는 함수를 따로 구현하여 모두 다 시행해보는 것으로 하였습니다.

재귀가 아닌 방법으로 해야 할까요? 그럼 무엇으로 해야할지 잘 모르겠습니다.

도움 부탁드립니다.

#include <cstdio>
#include <memory.h>
int max(int a, int b) { return a > b ? a : b; }
int N, board[20][20], ans;
void UP() {
	bool joined[20][20] = { false };
	int i, j;
	int r, c;
	for (j = 0; j < N; j++) {
		for (i = 1; i < N; i++) {
			r = i;
			if (board[r][j] == 0) continue;
			while (board[r - 1][j] == 0 && r > 0) {
				board[r - 1][j] = board[r][j];
				board[r][j] = 0;
				r--;
			}
			if (r == 0) continue;
			if (board[r][j] == board[r - 1][j] && !joined[r - 1][j]) {
				joined[r - 1][j] = true;
				board[r - 1][j] *= 2;
				board[r][j] = 0;
				ans = max(ans, board[r - 1][j]);
			}
		}
	}
}
void L() {
	bool joined[20][20] = { false };
	int i, j;
	int r, c;
	for (i = 0; i < N; i++) {
		for (j = 1; j < N; j++) {
			c = j;
			if (board[i][c] == 0) continue;
			while (board[i][c - 1] == 0 && c > 0) {
				board[i][c - 1] = board[i][c];
				board[i][c] = 0;
				c--;
			}
			if (c == 0) continue;
			if (board[i][c] == board[i][c - 1] && !joined[i][c - 1]) {
				joined[i][c - 1] = true;
				board[i][c - 1] *= 2;
				board[i][c] = 0;
				ans = max(ans, board[i][c - 1]);
			}
		}
	}
}
void R() {
	bool joined[20][20] = { false };
	int i, j;
	int r, c;
	for (i = 0; i < N; i++) {
		for (j = N - 2; j >= 0; j--) {
			c = j;
			if (board[i][c] == 0) continue;
			while (board[i][c + 1] == 0 && c < N - 1) {
				board[i][c + 1] = board[i][c];
				board[i][c] = 0;
				c++;
			}
			if (c == N - 1) continue;
			if (board[i][c] == board[i][c + 1] && !joined[i][c + 1]) {
				joined[i][c + 1] = true;
				board[i][c + 1] *= 2;
				board[i][c] = 0;
				ans = max(ans, board[i][c + 1]);
			}
		}
	}
}
void DW() {
	bool joined[20][20] = { false };
	int i, j;
	int r, c;
	for (j = 0; j < N; j++) {
		for (i = N - 2; i >= 0; i--) {
			r = i;
			if (board[r][j] == 0) continue;
			while (board[r + 1][j] == 0 && r < N - 1) {
				board[r + 1][j] = board[r][j];
				board[r][j] = 0;
				r++;
			}
			if (r == N - 1) continue;
			if (board[r][j] == board[r + 1][j] && !joined[r+1][j]) {
				joined[r + 1][j] = true;
				board[r + 1][j] *= 2;
				board[r][j] = 0;
				ans = max(ans, board[r + 1][j]);
			}
		}
	}
}
void sim(int remain) {
	if (remain == 0) return;
	int origin[20][20];
	memcpy(origin, board, sizeof(origin));
	// up
	UP();
	sim(remain - 1);
	memcpy(board, origin, sizeof(origin));
	// L
	L();
	sim(remain - 1);
	memcpy(board, origin, sizeof(origin));
	// R
	R();
	sim(remain - 1);
	memcpy(board, origin, sizeof(origin));
	// dw
	DW();
	sim(remain - 1);
}
int main() {
	scanf("%d", &N);
	int i, j;
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
			ans = max(ans, board[i][j]);
		}
	sim(10);
	printf("%d", ans);
	return 0;
}

sung1104hyun 7년 전 28

저는 이동했을때 변화가 없을경우 같은방향을 추가적으로 탐색하지 않는 방법과

최대값을 계속 갱신 시켜주면서 현재 Depth에서 최대값에 절대 도달할 수 없다고 판단되는 경우 가지치기하는 방법으로 해서 AC받았습니당..

예를들어 10번 이동했을때 현재 가지고있는 최대값이 1024이라면

바로 전 Depth에서 최대값을 512이하로 가지는 경우

그 이전 Depth에서 최대값을 256이하로 가지는 경우

등은 더이상 뻗어나가는게 의미가없게 됩니다.

zxcv1534 7년 전 2

정말 감사합니다!

덕분에 정답을 받을 수 있었습니다.

dotorya 7년 전 3

저도 덕분에 시간초과 해결했습니다. 감사합니다!!

cokcjswo 6년 전 0

저도 참고해서 시간초과 해결했어요 ㅠㅠㅠㅠㅠㅠ 감사합니다 !!!!

seni 6년 전 0

감사합니다 ㅠㅠㅠㅠㅠㅠ 첫번째 거르기 조건은 생각해냈는데 미처 생각못한 두번째 조건 덕분에 해결됐어요

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

문제

문제

출처

ICPC

시간초과 어떻게 해결하여야 할까요?

zxcv1534 7년 전 1

sung1104hyun 7년 전 28

zxcv1534 7년 전 2

dotorya 7년 전 3

cokcjswo 6년 전 0

seni 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말