글 읽기 - 2048 열시간째 풀다지쳐서... 흑 완전탐색 4프로 오답, 오류가 뭘까요?

frigrammer 6년 전 0

오답의 이유가 뭘까요?

완전탐색하는 표를 만들고 ( 위위위위위 ,위위위위왼, .... 오른오른오른오른오른) <-이런느낌으로 만들었는데

원래 테이블을 복사하고,

복사한 테이블을 표대로 이동하고,

제일 큰 블록을 찾아서 출력했는데 계속 4프로에서 오답이 나오네요..

열시간째 풀다 지쳐 질문올립니다.

도대체 무슨 오류가 있는걸까요?

#include <iostream>
#include <algorithm>

using namespace std;


int testLoop[1024][5] = { 0, };
int arr[21][21] = { 0, };
int width = 0;
int sol = 0;

const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;
const int UP = 4;

int comp(int a, int b) {
	if (a == 0 && b > 0) {
		return 0;
	}
	if (a > 0 && b == 0) {
		return 1;
	}
	return 0;
}

int revComp(int a, int b) {
	if (a == 0 && b > 0) {
		return 1;
	}
	if (a > 0 && b == 0) {
		return 0;
	}
	return 0;
}

int findSum(int inputVal) {
	int copyArr[21][21] = { 0, };

	//테이블 복사
	for (int j = 0; j < width; j++) {
		for (int i = 0; i < width; i++) {
			copyArr[j][i] = arr[j][i];
		}
	}

	int copyCrossArr[21][21] = { 0, };

	//오른쪽이면 오른쪽으로 왼쪽이면 왼쪽으로 밀어줌
	//위아래는 sort으로 밀어줄 수 없음, 그래서 먼저 행과열을 바꿔준뒤에 밀고, 밀어준 것을 다시 행과열을 바꿔서 넣어줌
	//sort에 사용되는 comp는 0과, 0이 아닌경우만 비교, 0이 아닌것만 비교해서 소팅함
	
	//testLoop는 완전 탐색 테이블 총 1024가지의 방향이 들어있음 RRRRR 부터 DDDDD까지
	//밀어줌
	for (int k = 0; k < 5; k++) {
		switch (testLoop[inputVal][k]) {	
		case RIGHT:
			for (int j = 0; j < width; j++) {
				sort(copyArr[j], copyArr[j] + width, revComp);
			}
			break;
		case LEFT:
			for (int j = 0; j < width; j++) {
				sort(copyArr[j], copyArr[j] + width, comp);
			}
			break;
		case DOWN:
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyCrossArr[i][j] = copyArr[j][i];
				}
			}
			for (int j = 0; j < width; j++) {
				sort(copyCrossArr[j], copyCrossArr[j] + width, revComp);
			}

			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyArr[j][i] = copyCrossArr[i][j];
				}
			}
			break;
		case UP:
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyCrossArr[i][j] = copyArr[j][i];
				}
			}
			for (int j = 0; j < width; j++) {
				sort(copyCrossArr[j], copyCrossArr[j] + width, comp);
			}
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyArr[j][i] = copyCrossArr[i][j];
				}
			}
			break;
		}

		//밀어준 후에 인접한 애들끼리 합함, 합해질 경우 한칸 건너 뜀.
		for (int j = 0; j < width; j++) {
			for (int i = 0; i < width; i++) {

				switch (testLoop[inputVal][k]) {
				case RIGHT:
					if (width - 1 - i - 1 >= 0)
						if (copyArr[j][width - 1 - i] == copyArr[j][width - 1 - i - 1]) {
							copyArr[j][width - 1 - i] *= 2;// copyArr[j][width - 1 - i - 1];
							copyArr[j][width - 1 - i - 1] = 0;
							i++;
						}
					break;

				case LEFT:
					if (i + 1<width)
						if (copyArr[j][i + 1] == copyArr[j][i]) {
							copyArr[j][i] *= 2;//copyArr[j][i + 1];
							copyArr[j][i + 1] = 0;
							i++;
						}
					break;
				case DOWN:
					if (width - 1 - i - 1 >= 0)
						if (copyArr[width - 1 - i][j] == copyArr[width - 1 - i - 1][j]) {
							copyArr[width - 1 - i][j] *= 2;//copyArr[width - 1 - i - 1][j];
							copyArr[width - 1 - i - 1][j] = 0;
							i++;
						}
					break;

				case UP:
					if (i + 1<width)
						if (copyArr[i + 1][j] == copyArr[i][j]) {
							copyArr[i][j] *= 2;// copyArr[i + 1][j];
							copyArr[i + 1][j] = 0;
							i++;
						}
					break;
				}
			}
		}

		//합해지고 난 후, 공백이 생기므로 다시 밀어줌
		switch (testLoop[inputVal][k]) {
		case RIGHT:
			for (int j = 0; j < width; j++) {
				sort(copyArr[j], copyArr[j] + width, revComp);
			}
			break;
		case LEFT:
			for (int j = 0; j < width; j++) {
				sort(copyArr[j], copyArr[j] + width, comp);
			}
			break;
		case DOWN:
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyCrossArr[i][j] = copyArr[j][i];
				}
			}
			for (int j = 0; j < width; j++) {
				sort(copyCrossArr[j], copyCrossArr[j] + width, revComp);
			}
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyArr[j][i] = copyCrossArr[i][j];
				}
			}
			break;
		case UP:
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyCrossArr[i][j] = copyArr[j][i];
				}
			}
			for (int j = 0; j < width; j++) {
				sort(copyCrossArr[j], copyCrossArr[j] + width, comp);
			}
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyArr[j][i] = copyCrossArr[i][j];
				}
			}
			break;
		}
	}

	int maxBlock = 0;

	//그 중 제일큰 블록을 찾음
	for (int j = 0; j < width; j++) {
		for (int i = 0; i < width; i++) {
			if (maxBlock < copyArr[j][i]) {
				maxBlock = copyArr[j][i];
				sol = inputVal;
			}
		}
	}

	return maxBlock;
}

int main() {
	int cnt = 0;
	//각 방향에 대한 완전탐색 테이블 작성
	for (int j = 0; j < 1024; j++) {
		int tmp = cnt;
		for (int i = 0; i < 5; i++) {
			testLoop[j][i] = tmp % 4 + 1;
			tmp /= 4;
		}
		cnt++;
	}
	cin >> width;

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

	int maxBlock = -1;
	int maxSol = -1;
	for (int k = 0; k < 1024; k++) {
		int tmp = findSum(k);	//모두 완전탐색해서 제일 큰 경우를 찾음
		if (maxBlock < tmp) {
			maxBlock = tmp;
			maxSol = sol;
		}
	}

	cout << maxBlock;//여기서 정답 출력
	/*
	//////////////////////////////여기 부턴 디버깅용 소스
	//	최단경로의 단계 보여줌
	cout << endl;
	cout << maxSol;
	cout << endl;

	int copyArr[21][21] = { 0, };
	int copyCrossArr[21][21];

	for (int j = 0; j < width; j++) {
		for (int i = 0; i < width; i++) {
			copyArr[j][i] = arr[j][i];
		}
	}

	for (int k = 0; k < 5; k++) {
		switch (testLoop[maxSol][k]) {
		case RIGHT:
			for (int j = 0; j < width; j++) {
				sort(copyArr[j], copyArr[j] + width, revComp);
			}
			break;
		case LEFT:
			for (int j = 0; j < width; j++) {
				sort(copyArr[j], copyArr[j] + width, comp);
			}
			break;
		case DOWN:
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyCrossArr[i][j] = copyArr[j][i];
				}
			}
			for (int j = 0; j < width; j++) {
				sort(copyCrossArr[j], copyCrossArr[j] + width, revComp);
			}

			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyArr[j][i] = copyCrossArr[i][j];
				}
			}
			break;
		case UP:
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyCrossArr[i][j] = copyArr[j][i];
				}
			}
			for (int j = 0; j < width; j++) {
				sort(copyCrossArr[j], copyCrossArr[j] + width, comp);
			}
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyArr[j][i] = copyCrossArr[i][j];
				}
			}
			break;
		}


		for (int j = 0; j < width; j++) {
			for (int i = 0; i < width; i++) {

				switch (testLoop[maxSol][k]) {
				case RIGHT:
					if (width - 1 - i - 1 >= 0)
						if (copyArr[j][width - 1 - i] == copyArr[j][width - 1 - i - 1]) {
							copyArr[j][width - 1 - i] *= 2;// copyArr[j][width - 1 - i - 1];
							copyArr[j][width - 1 - i - 1] = 0;
							i++;
						}
					break;

				case LEFT:
					if (i + 1<width)
						if (copyArr[j][i + 1] == copyArr[j][i]) {
							copyArr[j][i] *= 2;// copyArr[j][i + 1];
							copyArr[j][i + 1] = 0;
							i++;
						}
					break;
				case DOWN:
					if (width - 1 - i - 1 >= 0)
						if (copyArr[width - 1 - i][j] == copyArr[width - 1 - i - 1][j]) {
							copyArr[width - 1 - i][j] *= 2;// copyArr[width - 1 - i - 1][j];
							copyArr[width - 1 - i - 1][j] = 0;
							i++;
						}
					break;

				case UP:
					if (i + 1<width)
						if (copyArr[i + 1][j] == copyArr[i][j]) {
							copyArr[i][j] *= 2;// copyArr[i + 1][j];
							copyArr[i + 1][j] = 0;
							i++;
						}
					break;
				}
			}
		}

		switch (testLoop[maxSol][k]) {
		case RIGHT:
			for (int j = 0; j < width; j++) {
				sort(copyArr[j], copyArr[j] + width, revComp);
			}
			break;
		case LEFT:
			for (int j = 0; j < width; j++) {
				sort(copyArr[j], copyArr[j] + width, comp);
			}
			break;
		case DOWN:
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyCrossArr[i][j] = copyArr[j][i];
				}
			}
			for (int j = 0; j < width; j++) {
				sort(copyCrossArr[j], copyCrossArr[j] + width, revComp);
			}
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyArr[j][i] = copyCrossArr[i][j];
				}
			}
			break;
		case UP:
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyCrossArr[i][j] = copyArr[j][i];
				}
			}
			for (int j = 0; j < width; j++) {
				sort(copyCrossArr[j], copyCrossArr[j] + width, comp);
			}
			for (int j = 0; j < width; j++) {
				for (int i = 0; i < width; i++) {
					copyArr[j][i] = copyCrossArr[i][j];
				}
			}
			break;
		}

		char c;
		switch (testLoop[maxSol][k]) {
		case RIGHT:
			c = 'R';
			break;
		case UP:
			c = 'U';
			break;
		case DOWN:
			c = 'D';
			break;
		case LEFT:
			c = 'L';
			break;
		}
		cout << c << " " << endl;

		for (int j = 0; j < width; j++) {
			for (int i = 0; i < width; i++) {
				cout << copyArr[j][i] << " ";
			}
			cout << endl;
		}
	}
	*/
	return 0;
}

cjscokdd 6년 전 0

저도 자꾸 4%에서 틀리네요 여기 올려주신 테스트케이스는 다 통과하는데 특정 테스트 케이스가 뭘지 궁금하네요 참... 저도 와드 박습니다.

frigrammer 6년 전 0

완전탐색하신 분들이 4프로에서 걸리는게 있는거 같은데... 발생할 수 있는 예외나 반례 같은게 있나 ㅠㅜ

답을 모르겠다 으아아

seico75 6년 전 0

sort 를 쓰다니 기발하네요. 근데 소트가 stable 보장이 안되는것 같은데 괜찮나요?

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

문제

문제

출처

ICPC

2048 열시간째 풀다지쳐서... 흑 완전탐색 4프로 오답, 오류가 뭘까요?

frigrammer 6년 전 0

cjscokdd 6년 전 0

frigrammer 6년 전 0

seico75 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말