글 읽기 - C++ 시간초과 (최적화) 질문입니다.

hidden987 3년 전 0

2차원 배열을 동적할당을 통해 복사하는 과정

또는 블럭을 지정 방향으로 이동 + 블럭 결합 코드쪽

둘중 한부분에서 시간이 많이 잡아먹히는것 같은데

어떻게 최적화 해야할지 감이 안오네요

코드 자체는 정답인데 여기서 방법이 없을까요?

#include <stdlib.h>
#include <iostream>
#include <stdio.h>
using namespace std;

int val_max = 0;
int val_lim;
int val_size;
int inf_dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int chk[20][20] = { 0 };
int val_multiply = 1024;
int val_chkLim = 11;
int val_tries = 10;

void task_play(int**, int);
bool task_chkCanMove(int**, int);
bool task_chkDifferent(int**, int**);
void task_shiftBlock(int**, int, int);
int task_findMax(int**);

int main()
{
	int map_size;
	int** map_inf;
	int tmp;

	scanf("%d", &map_size);
	map_inf = new int* [map_size];
	for (int i = 0; i < map_size; i++) map_inf[i] = new int[map_size];
	for (int i = 0; i < map_size; i++) for (int j = 0; j < map_size; j++) scanf("%d", &map_inf[i][j]);

	val_size = map_size;
	tmp = task_findMax(map_inf);
	val_lim = tmp * val_multiply;
	task_play(map_inf, 1);
	if (val_max == 0) val_max = tmp;

	printf("%d", val_max);

	for (int i = 0; i < map_size; i++) delete[] map_inf[i];
	delete[] map_inf;

	return 0;
}
void task_play(int** map_inf, int val_turn)
{
	int tmp_max;
	int cX, cY;
	int** map_copy;
	map_copy = nullptr;

	if (val_turn > val_tries) {
		tmp_max = task_findMax(map_inf);
		if (val_max < tmp_max) val_max = tmp_max;
		return;
	}
	if (task_chkCanMove(map_inf, val_turn)) return;

	for (int i = 0; i < 4; i++) {
		cY = inf_dir[i][0];
		cX = inf_dir[i][1];
		
		map_copy = new int* [val_size]; for (int j = 0; j < val_size; j++) map_copy[j] = new int[val_size];
		for (int j = 0; j < val_size; j++) std::copy(map_inf[j], map_inf[j] + val_size, map_copy[j]);
		task_shiftBlock(map_copy, cY, cX);
		if (task_chkDifferent(map_inf, map_copy)) task_play(map_copy, val_turn + 1);
		for (int j = 0; j < val_size; j++) delete[] map_copy[j];
		delete[] map_copy;
	}
}
bool task_chkCanMove(int** arr, int turn)
{
	int tmp_max;
	int tmp_sum;
	int tmp_lim;
	
	tmp_max = 0;
	tmp_sum = 0;

	for (int i = 0; i < val_size; i++)
		for (int j = 0; j < val_size; j++) {
			tmp_sum += arr[i][j];
			if (tmp_max < arr[i][j]) tmp_max = arr[i][j];
		}

	if (val_max > 0){
		tmp_lim = val_max;
		for (int i = 0; i < val_chkLim - turn; i++) tmp_lim /= 2;
		if (tmp_lim >= tmp_max) return true;
	}

	if (tmp_max * 2 > tmp_sum) {
		if (val_max < tmp_max) val_max = tmp_max;
		return true;
	}
	return false;
}
bool task_chkDifferent(int** base, int** copy)
{
	for (int i = 0; i < val_size; i++)
		for (int j = 0; j < val_size; j++)
			if (base[i][j] != copy[i][j]) return true;
	return false;
}
void task_shiftBlock(int** map_inf, int addY, int addX)
{
	int cX;
	int cY;

	for (int i = 0; i < val_size; i++) for (int j = 0; j < val_size; j++) chk[i][j] = 0;

	if (addY == 1) {
		for (int y = val_size - 2; y >= 0; y--)
			for (int x = 0; x < val_size; x++){
				if (map_inf[y][x] == 0) continue;
				cY = y;
				while (cY + 1 < val_size && map_inf[cY + 1][x] == 0) cY++;
				if (cY + 1 < val_size && map_inf[y][x] == map_inf[cY + 1][x] && chk[cY][x] == 0) {
					map_inf[cY + 1][x] *= 2;
					map_inf[y][x] = 0;
					chk[cY][x] = 1;
				}
				else if (map_inf[cY][x] == 0) {
					map_inf[cY][x] = map_inf[y][x];
					map_inf[y][x] = 0;
				}
			}
	}
	else if (addY == -1) {
		for (int y = 1; y < val_size; y++)
			for (int x = 0; x < val_size; x++) {
				if (map_inf[y][x] == 0) continue;
				cY = y;
				while (cY - 1 >= 0 && map_inf[cY - 1][x] == 0) cY--;
				if (cY - 1 >= 0 && map_inf[y][x] == map_inf[cY - 1][x] && chk[cY][x] == 0) {
					map_inf[cY - 1][x] *= 2;
					map_inf[y][x] = 0;
					chk[cY][x] = 1;
				}
				else if (map_inf[cY][x] == 0) {
					map_inf[cY][x] = map_inf[y][x];
					map_inf[y][x] = 0;
				}
			}
	}
	if (addX == 1) {
		for (int x = val_size - 2; x >= 0; x--)
			for (int y = 0; y < val_size; y++) {
				if (map_inf[y][x] == 0) continue;
				cX = x;
				while (cX + 1 < val_size && map_inf[y][cX + 1] == 0) cX++;
				if (cX + 1 < val_size && map_inf[y][x] == map_inf[y][cX + 1] && chk[y][cX] == 0) {
					map_inf[y][cX + 1] *= 2;
					map_inf[y][x] = 0;
					chk[y][cX] = 1;
				}
				else if (map_inf[y][cX] == 0) {
					map_inf[y][cX] = map_inf[y][x];
					map_inf[y][x] = 0;
				}
			}
	}
	else if (addX == -1) {
		for (int x = 1; x < val_size; x++)
			for (int y = 0; y < val_size; y++) {
				if (map_inf[y][x] == 0) continue;
				cX = x;
				while (cX - 1 >= 0 && map_inf[y][cX - 1] == 0) cX--;
				if (cX - 1 >= 0 && map_inf[y][x] == map_inf[y][cX - 1] && chk[y][cX] == 0) {
					map_inf[y][cX - 1] *= 2;
					map_inf[y][x] = 0;
					chk[y][cX] = 1;
				}
				else if (map_inf[y][cX] == 0) {
					map_inf[y][cX] = map_inf[y][x];
					map_inf[y][x] = 0;
				}
			}
	}
}
int task_findMax(int** arr)
{
	int tmp;

	tmp = 0;
	for (int i = 0; i < val_size; i++) for (int j = 0; j < val_size; j++) if (tmp < arr[i][j]) tmp = arr[i][j];
	if (tmp == val_lim) {
		printf("%d", val_lim);
		exit(0);
	}

	return tmp;
}

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

문제

문제

출처

ICPC

C++ 시간초과 (최적화) 질문입니다.

hidden987 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말