글 읽기 - 풀긴했지만 다른 방식으로 하였을때 안되는 이유를 모르겠습니다.

rytkd88 4년 전 0

이동하는 중에 먼저 결합을 하였다면 다음번엔 결합하지 않는다는 예외처리 방식을 저는 처음에는 값이 들어있는 배열에 -1을 넣고 그것을 이용하여 판별하는 방식을 사용하였는데 정말 질문게시판의 모든 예시를 해봐도 반례가 안되는데 정답이 안떴습니다. 그래서 뭔가 찜찜하지만 이것을 체크 배열을 사용하여 따로 flag처리를 해주었더니 통과는 되었습니다. 하지만 위의 방식이 어떤부분에서 안되는지 알수가 없어서 너무 찜찜합니다. 혹시 알 수 있을까요..

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> pa;
int N;

int map[23][23];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int ans = 0;

void moving(int y, int x, int dir)
{
	int ny, nx;
	while (1)
	{
		ny = y + dy[dir];
		nx = x + dx[dir];
		if (ny >= 0 && ny < N && nx >= 0 && nx < N)
		{
			if (map[ny][nx] == 0)
			{
				map[ny][nx] = map[y][x];
				map[y][x] = 0;
				y = ny;
				x = nx;
			}
			else if (map[ny][nx] == -1)
			{
				map[ny][nx] = map[y][x];
				map[y][x] = 0;
				break;
			}
			else if (map[ny][nx] == map[y][x])
			{
				map[ny][nx] *= 2;
				map[y][x] = -1;
				break;
			}
			else
			{
				break;
			}
		}
		else
		{
			break;
		}
	}
}
void move(int dir) //전역 map을 이동
{
	switch (dir)
	{
	case 0:
		for (int k = N - 2; k >= 0; k--)
		{
			for (int p = 0; p < N; p++)
			{
				moving(k, p, dir);
			}
		}
		break;
	case 1:
		for (int k = 1; k < N; k++)
		{
			for (int p = 0; p < N; p++)
			{
				moving(k, p, dir);
			}
		}
		break;
	case 2:
		for (int k = 0; k < N; k++)
		{
			for (int p = N - 2; p >= 0; p--)
			{
				moving(k, p, dir);
			}
		}
		break;
	case 3:
		for (int k = 0; k < N; k++)
		{
			for (int p = 1; p < N; p++)
			{
				moving(k, p, dir);
			}
		}
		break;
	}
}
void solve(int dp) {

	if (dp == 5)
	{
		for (int a = 0; a < N; a++)
		{
			for (int b = 0; b < N; b++)
			{
				if (ans < map[a][b]) ans = map[a][b];
			}
		}
		return;
	}

	dp++;
	int now[21][21];
	//각 구간별 저장
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			now[i][j] = map[i][j];
		}
	}
	for (int i = 0; i < 4; i++)
	{
		move(i);
		solve(dp);
		for (int a = 0; a < N; a++) //now로 다시 돌려놓고 새로탐색
		{
			for (int b = 0; b < N; b++)
			{
				map[a][b] = now[a][b];
			}
		}
	}
}
int main()
{
	cin >> N;
	int smax = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
			if (map[i][j] > smax) smax = map[i][j];
		}
	}
	solve(0);

	cout << ans;
	return 0;
}

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

문제

문제

출처

ICPC

풀긴했지만 다른 방식으로 하였을때 안되는 이유를 모르겠습니다.

rytkd88 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말