글 읽기 - 틀린 예제를 발견했는데 틀린 이유를 모르겠습니다

nmy2511 6년 전 0

12100번 문제에서

자꾸 틀려서 검색도중에

10
16 16 8 32 32 0 0 8 8 8
16 0 0 0 0 8 0 0 0 16
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

위 케이스를 테스트할때 원래 64가 나와야하는데 128이나옵니다

최대 4번까지만 밀면 64가 나오기는 하는데 이러면 다른 케이스가 틀려서 이 문제는 아닌것 같고

구현한 코드에 문제가 있는것 같은데 제가 어느 부분이 문제가 있는지 잘 모르겠습니다.

문제가 되는 부분을 알려주신다면 감사하겠습니다.

#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector < vector<int>> v;
stack<pair<int, int>> sta;
bool check[20][20];

int final;
void left(int n, int now, vector<vector<int>> in);
void up(int n, int now, vector<vector<int>> in);
void down(int n, int now, vector<vector<int>> in);

void show(int n,vector<vector<int>> ve)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			printf("%d ", ve[i][j]);
		printf("\n");
	}
}

void right(int n, int now,vector<vector<int>> in)
{
	if (now == 5)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (in[i][j] > final)
					final = in[i][j];
			}
		}

		return;
	}
	vector<vector<int>> arr;
	arr = in;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			if (arr[i][j] == 0)
				continue;
			if (arr[i][j + 1] == 0)
			{
				arr[i][j + 1] = arr[i][j];
				arr[i][j] = 0;
			}
			else if (arr[i][j] == arr[i][j + 1] && check[i][j]==false)
			{
				arr[i][j + 1] = arr[i][j] * 2;
				arr[i][j] = 0;
				check[i][j + 1] = true;
				sta.push(make_pair(i, j + 1));
			}
		}
	}
	while (!sta.empty())
	{
		pair<int, int> temp = sta.top();
		check[temp.first][temp.second] = false;
		sta.pop();
	}

	left(n, now + 1, arr);
	right(n, now + 1, arr);
	up(n, now + 1, arr);
	down(n, now + 1, arr);
}

void left(int n, int now, vector<vector<int>> in)
{
	if (now == 5)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (in[i][j] > final)
					final = in[i][j];
			}
		}

		return;
	}
	vector<vector<int>> arr;
	arr = in;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			check[i][j] = 0;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = n-1; j > 0; j--)
		{
			if (arr[i][j] == 0)
				continue;
			if (arr[i][j - 1] == 0)
			{
				arr[i][j - 1] = arr[i][j];
				arr[i][j] = 0;
			}
			else if (arr[i][j] == arr[i][j - 1] && check[i][j] == false)
			{
				arr[i][j - 1] = arr[i][j] * 2;
				arr[i][j] = 0;
				check[i][j - 1] = true;
				sta.push(make_pair(i, j - 1));
			}
		}
	}
	while (!sta.empty())
	{
		pair<int, int> temp = sta.top();
		check[temp.first][temp.second] = false;
		sta.pop();
	}

	left(n, now + 1, arr);
	right(n, now + 1, arr);
	up(n, now + 1, arr);
	down(n, now + 1, arr);
}

void down(int n, int now, vector<vector<int>> in)
{
	if (now == 5)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (in[i][j] > final)
					final = in[i][j];
			}
		}

		return;
	}
	vector<vector<int>> arr;
	arr = in;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			check[i][j] = 0;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1; j++)
		{
			if (arr[j][i] == 0)
				continue;
			if (arr[j+1][i] == 0)
			{
				arr[j+1][i] = arr[j][i];
				arr[j][i] = 0;
			}
			else if (arr[j][i] == arr[j+1][i] && check[j][i] == false)
			{
				arr[j+1][i] = arr[j][i] * 2;
				arr[j][i] = 0;
				check[j+1][i] = true;
				sta.push(make_pair(j + 1, i));
			}
		}
	}
	while (!sta.empty())
	{
		pair<int, int> temp = sta.top();
		check[temp.first][temp.second] = false;
		sta.pop();
	}

	left(n, now + 1, arr);
	right(n, now + 1, arr);
	up(n, now + 1, arr);
	down(n, now + 1, arr);
}

void up(int n, int now, vector<vector<int>> in)
{
	if (now == 5)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (in[i][j] > final)
					final = in[i][j];
			}
		}

		return;
	}
	vector<vector<int>> arr;
	arr = in;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			check[i][j] = 0;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = n-1; j > 0; j--)
		{
			if (arr[j][i] == 0)
				continue;
			if (arr[j - 1][i] == 0)
			{
				arr[j - 1][i] = arr[j][i];
				arr[j][i] = 0;
			}
			else if (arr[j][i] == arr[j - 1][i] && check[j][i] == false)
			{
				arr[j - 1][i] = arr[j][i] * 2;
				arr[j][i] = 0;
				check[j - 1][i] = true;
				sta.push(make_pair(j - 1, i));
			}
		}
	}
	while (!sta.empty())
	{
		pair<int, int> temp = sta.top();
		check[temp.first][temp.second] = false;
		sta.pop();
	}

	left(n, now + 1, arr);
	right(n, now + 1, arr);
	up(n, now + 1, arr);
	down(n, now + 1, arr);
}


int main()
{
	int n;
	scanf("%d", &n);
	v.resize(n + 1);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int t;
			scanf("%d", &t);
			v[i].push_back(t);
		}
	}

	left(n, 0, v);
	right(n, 0, v);
	up(n, 0, v);
	down(n, 0, v);

	printf("%d", final);
}

rlaalswo01 6년 전 0

코드를 다 분석하긴 힘들지만, 저 같은 경우도 올려주신 테스트케이스를 돌려보니 똑같이 128이 나오는 문제가 발생해서 흥미로워서 제 코드를 분석한 결과를 말씀드리자면,

예를 들어 64 , 32, 32 세 개의 수가 한 줄에 있을 때 오른 쪽으로 밀면 0, 64, 64 가 되어야 하는데, 제가 작성한 코드는 32 두개가 합쳐져서 64가 된 다음 다시 왼쪽에서 오는 64가 합쳐져서 128이 되더군요. 그런 식으로 연쇄(?) 합성이 이뤄지다보니 다섯번 안에 128을 만들어버리게 되는거죠...

흠 전 그 문제를 해결했는데도 채점 해보면 틀렸다고 나오네요 ㅡㅡ

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

문제

문제

출처

ICPC

틀린 예제를 발견했는데 틀린 이유를 모르겠습니다

nmy2511 6년 전 0

rlaalswo01 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말