글 읽기 - 시간초과가 뜹니다..

bbwwpark 4년 전 0

제가 계산한 시간복잡도는 아래와 같습니다.

4방향으로 5번 작동하는 모든 경우의수 4^5 = 1024

작동하는 경우의 수마다 걸리는 시간 : 400(번119줄 - go 함수 2차원 매개변수 복사) + 1600(126번줄 - 4방향 탐색을 위한 2차원 배열 복사) + 800(8번줄 - moving 함수에서 moving, merge 각각 최대 400번 연산소요)

총 시간 복잡도 = 4방향으로 5번 작동하는 모든 경우의수 * 작동하는 경우의 수마다 걸리는 시간 = 1024 * 2800 = 2,867,200

이렇게 계산이 되어서 시간초과 문제는 없을 거라고 생각했는데 시간초과가 나네요..

제가 계산한 방식이 잘못된거 같지만 뭐가 잘못됐는지 잘모르겠습니다.

가르쳐주시면 감사하겠습니다.

#include<iostream>
#include<algorithm>
using namespace std;

int n;
int res = -1;

void moving(int dir, int map[][20]) {//0123 동서남북
	if (dir == 0) { //동쪽으로 이동 
		//moving
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j]) {
					for (int k = j; k < n-1; k++) {
						if (map[i][k + 1] == 0)
							swap(map[i][k], map[i][k + 1]);
					}
				}
			}
		}
		//merge
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j >= 1; j--) {
				if (map[i][j] == map[i][j - 1]) {
					map[i][j] *= 2;
					res = max(res, map[i][j]);
					map[i][j - 1] = 0;
					for (int k = n-1; k >= 1; k--) {
						if (map[i][k] == 0 && map[i][k-1])
							swap(map[i][k], map[i][k - 1]);
					}
				}
			}
		}
	}
	else if (dir == 1) { //서쪽으로 이동
		//moving
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <n; j++) {
				if (map[i][j]) {
					for (int k = j; k >= 1; k--) {
						if (map[i][k - 1] == 0)
							swap(map[i][k], map[i][k - 1]);
					}
				}
			}
		}
		//merge
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n-1; j++) {
				if (map[i][j] == map[i][j + 1]) {
					map[i][j] *= 2;
					res = max(res, map[i][j]);
					map[i][j + 1] = 0;
					for (int k = 0; k <n-1; k++) {
						if (map[i][k] == 0 && map[i][k + 1])
							swap(map[i][k], map[i][k + 1]);
					}
				}
			}
		}
	}
	else if (dir == 2) { //남쪽으로 이동
		//moving
		for (int j = 0; j < n; j++) {
			for (int i = n-1; i >= 0; i--) {
				if (map[i][j]) {
					for (int k = i; k <n-1; k++) {
						if(map[k][j] && map[k+1][j] == 0)
							swap(map[k][j], map[k + 1][j]);
					}
				}
			}
		}
		//merge
		for (int j = 0; j < n; j++) {
			for (int i = n-1; i >=0; i--) {
				if (map[i][j] == map[i - 1][j]) {
					map[i][j] *= 2;
					res = max(res, map[i][j]);
					map[i - 1][j] = 0;
					for (int k = n - 1; k >= 1; k--) {
						if (map[k][j] == 0 && map[k - 1][j])
							swap(map[k][j], map[k - 1][j]);
					}
				}
			}
		}
	}
	else if (dir == 3) { //북쪽으로 이동
		//moving
		for (int j = 0; j < n; j++) {
			for (int i = 0; i < n; i++) {
				if (map[i][j]) {
					for (int k = i; k >=1; k--) {
						if (map[k][j] && map[k - 1][j] == 0)
							swap(map[k][j], map[k - 1][j]);
					}
				}
			}
		}
		//merge
		for (int j = 0; j < n; j++) {
			for (int i = 0; i < n; i++) {
				if (map[i][j] == map[i + 1][j]) {
					map[i][j] *= 2;
					res = max(res, map[i][j]);
					map[i + 1][j] = 0;
					for (int k = 0; k <n-1; k++) {
						if (map[k][j] == 0 && map[k + 1][j])
							swap(map[k][j], map[k + 1][j]);
					}
				}
			}
		}
	}
}

void go(int cnt, int map[][20]) {

	if (cnt >= 5) return;
	
	int next_map[20][20];

	for (int i = 0; i < 4; i++) {
		copy(&map[0][0], &map[n - 1][n - 1] + 1, &next_map[0][0]);
		moving(i, next_map);
		go(cnt + 1, next_map);
	}
}

int main() {
	cin >> n;

	int map[20][20];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			res = max(res, map[i][j]);
		}
	}

	go(0,map);

	printf("%d", res);
	return 0;
}

bbwwpark 4년 전 0

copy 시 배열범위를 초과하는 접근으로 UB가 발생하여 시간초과 현상이 떴었습니다.

아래와 같이 수정하여 정답처리 됐습니다.

129줄의 memcpy를 통해 해보니 틀렸습니다가 뜨네요.

128줄과 129줄 같은 동작을 하는 것 아닌가요?

어느 부분에서 놓치고 있는지 모르겠습니다.

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int n;
int res = -1;

void moving(int dir, int map[][21]) {//0123 동서남북
	if (dir == 0) { //동쪽으로 이동 
		//moving
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j]) {
					for (int k = j; k < n - 1; k++) {
						if (map[i][k + 1] == 0)
							swap(map[i][k], map[i][k + 1]);
					}
				}
			}
		}

		//sum
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j >= 1; j--) {
				if (map[i][j] == map[i][j - 1]) {
					map[i][j] *= 2;
					res = max(res, map[i][j]);
					map[i][j - 1] = 0;
					for (int k = n - 1; k >= 1; k--) {
						if (map[i][k] == 0 && map[i][k - 1])
							swap(map[i][k], map[i][k - 1]);
					}
				}
			}
		}
	}
	else if (dir == 1) { //서쪽으로 이동
		//moving
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j]) {
					for (int k = j; k >= 1; k--) {
						if (map[i][k - 1] == 0)
							swap(map[i][k], map[i][k - 1]);
					}
				}
			}
		}
		//sum
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n - 1; j++) {
				if (map[i][j] == map[i][j + 1]) {
					map[i][j] *= 2;
					res = max(res, map[i][j]);
					map[i][j + 1] = 0;
					for (int k = 0; k < n - 1; k++) {
						if (map[i][k] == 0 && map[i][k + 1])
							swap(map[i][k], map[i][k + 1]);
					}
				}
			}
		}
	}
	else if (dir == 2) { //남쪽으로 이동

		for (int j = 0; j < n; j++) {
			for (int i = n - 1; i >= 0; i--) {
				if (map[i][j]) {
					for (int k = i; k < n - 1; k++) {
						if (map[k][j] && map[k + 1][j] == 0)
							swap(map[k][j], map[k + 1][j]);
					}
				}
			}
		}

		for (int j = 0; j < n; j++) {
			for (int i = n - 1; i >= 0; i--) {
				if (map[i][j] == map[i - 1][j]) {
					map[i][j] *= 2;
					res = max(res, map[i][j]);
					map[i - 1][j] = 0;
					for (int k = n - 1; k >= 1; k--) {
						if (map[k][j] == 0 && map[k - 1][j])
							swap(map[k][j], map[k - 1][j]);
					}
				}
			}
		}
	}
	else if (dir == 3) { //북쪽으로 이동
		//moving
		for (int j = 0; j < n; j++) {
			for (int i = 0; i < n; i++) {
				if (map[i][j]) {
					for (int k = i; k >= 1; k--) {
						if (map[k][j] && map[k - 1][j] == 0)
							swap(map[k][j], map[k - 1][j]);
					}
				}
			}
		}

		for (int j = 0; j < n; j++) {
			for (int i = 0; i < n; i++) {
				if (map[i][j] == map[i + 1][j]) {
					map[i][j] *= 2;
					res = max(res, map[i][j]);
					map[i + 1][j] = 0;
					for (int k = 0; k < n - 1; k++) {
						if (map[k][j] == 0 && map[k + 1][j])
							swap(map[k][j], map[k + 1][j]);
					}
				}
			}
		}
	}
}

void go(int cnt, int map[][21]) {

	if (cnt >= 5) return;

	int next_map[21][21];

	for (int i = 0; i < 4; i++) {
		copy(&map[0][0], &map[n - 1][n - 1] + 1, &next_map[0][0]);
		//memcpy(next_map, map, sizeof(map));
		moving(i, next_map);
		go(cnt + 1, next_map);
	}
}

int main() {
	cin >> n;

	int map[21][21];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			res = max(res, map[i][j]);
		}
	}

	go(0, map);

	printf("%d", res);
	return 0;
}

evenharder 4년 전 1

map이 int 21개 배열을 가리키는 포인터이기 때문에 sizeof(map)이 8이 될 것으로 예상됩니다. 저렇게 함수로 전달할 때 sizeof는 map의 실제 유효한 크기를 계산할 수 없습니다.

sizeof(next_map)으로 하면 잘 동작하리라 생각합니다.

bbwwpark 4년 전 1

@evenharder

감사합니다. 이해되었습니다.

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

문제

문제

출처

ICPC

시간초과가 뜹니다..

bbwwpark 4년 전 0

bbwwpark 4년 전 0

evenharder 4년 전 1

bbwwpark 4년 전 1

감사합니다. 이해되었습니다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말