글 읽기 - 질문있습니다. 반례를 모르겠습니다.

minjae200 5년 전 0

질문게시판에 있는 테스트케이스들 데이터를 넣었을경우 모든 답이 출력됩니다. (설명은 주석을 참고해주세요)

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

#define MAX_SIZE 25

int N, map[MAX_SIZE][MAX_SIZE];
int ans;

//이 문제에서 가장중요한 함수 (합치기)
void merge(int dir)
{
	queue<int> q;


	//상하좌우 4가지 경우에 대해서 (각각 합쳐지는 룰이 다르므로)
	switch (dir)
	{
		//상
	case 0:
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {

				//0인경우에는 q에 넣지 않는다.
				if (map[j][i] != 0) q.push(map[j][i]);
				map[j][i] = 0;
			}

			//'상'인경우 idx는 0부터 N-1까지 
			int idx = 0;
			while (!q.empty()) {
				int pop_data = q.front();
				q.pop();
				
				//0이면 그냥 pop한 data 넣고
				if (map[idx][i] == 0) map[idx][i] = pop_data;
				//같다면 합쳐질수 있으므로 2배해서 넣고
				else if (map[idx][i] == pop_data) map[idx++][i] *= 2;
				//모두 아니라면 그냥 pop한 data넣고
				else map[++idx][i] = pop_data;
			}
		}
		break;
		//하
	case 1:
		for (int i = 0; i < N; i++) {
			for (int j = N - 1; j >= 0; j--) {
				if (map[j][i] != 0) q.push(map[j][i]);
				map[j][i] = 0;
			}
			int idx = N - 1;
			while (!q.empty()) {
				int pop_data = q.front();
				q.pop();

				if (map[idx][i] == 0) map[idx][i] = pop_data;
				else if (map[idx][i] == pop_data) map[idx--][i] *= 2;
				else map[--idx][i] = pop_data;
			}
		}
		break;
		//좌
	case 2:
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0) q.push(map[i][j]);
				map[i][j] = 0;
			}
			int idx = 0;
			while (!q.empty()) {
				int pop_data = q.front();
				q.pop();

				if (map[i][idx] == 0) map[i][idx] = pop_data;
				else if (map[i][idx] == pop_data) map[i][idx++] *= 2;
				else map[i][++idx] = pop_data;
			}
		}
		break;
		//우
	case 3:
		for (int i = 0; i < N; i++) {
			for (int j = N - 1; j >= 0; j--) {
				if (map[i][j] != 0) q.push(map[i][j]);
				map[i][j] = 0;

				int idx = N - 1;
				while (!q.empty()) {
					int pop_data = q.front();
					q.pop();

					if (map[i][idx] == 0) map[i][idx] = pop_data;
					else if (map[i][idx] == pop_data) map[i][idx--] *= 2;
					else map[i][--idx] = pop_data;
				}
			}
		}
		break;
	}
}

// copy하는 함수
void copy(int (*arr)[MAX_SIZE], int (*arr2)[MAX_SIZE])
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			arr[i][j] = arr2[i][j];
		}
	}
}

void dfs(int depth)
{
	//최대 5번 움직여서 얻을 수 있는 최대값이므로 depth가 5일때 map전체를 탐색하며 최대값을 찾아준다.
	if (depth == 5) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] > ans) ans = map[i][j];
			}
		}
		return;
	}
	//backtracking을 사용하기 위해서 copymap 선언
	int copymap[MAX_SIZE][MAX_SIZE];
	//copymap에 map을 copy한다.
	copy(copymap, map);
	for (int i = 0; i < 4; i++) {
		//2048게임에서 상하좌우 합치는 함수
		merge(i);
		//dfs 호출
		dfs(depth + 1);
		//다시 되돌리기 (backtracking)
		copy(map, copymap);
	}
}

//문제 데이터 입력받기
void input(void)
{
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
}

int main(void)
{
	//문제 데이터를 입력받는다.
	input();
	//dfs로 가능한 경우를 모두 시도해본다.
	dfs(0);
	//멕시멈값을 출력한다.
	cout << ans << endl;
	return 0;
}

djm03178 5년 전 0

가능한 작은 케이스로 반례 만들어서 드립니다. N=2로는 2000개 정도 랜덤 케이스를 돌려봤지만 반례가 나오지 않는 것 같습니다.

3
32 0 0
0 256 4
256 2 512
output: 1024
correct answer: 512

3
32 1024 128
1024 2 16
2 1024 0
output: 1024
correct answer: 2048

3
2 1024 256
512 64 512
32 4 1024
output: 2048
correct answer: 1024

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

문제

문제

출처

ICPC

질문있습니다. 반례를 모르겠습니다.

minjae200 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말