글 읽기 - 틀렸는데 맞았다고 뜨는 것 같습니다.

clrmt 4년 전 0

EASY버전은 맞았고, HARD버전에서 depth수와 배열 크기만 늘렸는데 틀렸습니다.

도무지 이유를 찾을 수가 없어서 블로그에 있던 정답 코드를 가져와서 약 1000개 이상의 랜덤 반례를 돌려보아도 전부 일치했습니다.

그러다가, 28번째 줄에서 현재 depth를 3으로 나누었을 때 1이 아닌 경우에는 4방향으로 탐색하고, 그 이외에는 이전 방향과 다른 3방향으로 탐색하였더니 AC를 받았습니다.

아마 방향 관련된 논리가 틀린 것 같은데, 직전에 갔던 방향으로 탐색하지 않는 것이 문제가 되나요?

#include <iostream>
using namespace std;

int board[12][21][21]; // depth, h, w, 각 depth마다 직전의 board를 읽고, 현재의 board에 씁니다.
int n;
int maxValue = 0;

void recurse(int depth, int lastDirection) {

	int d;
	int i, j, k;
	int t;

    // 종료조건
	if (depth >= 11) {
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
                // 가장 큰 숫자를 찾기 위한 비트 or연산.
				maxValue |= board[depth - 1][i][j];
			}
		}
		return;
	}

	t = 0;

    // 방향에 따른 분기
	for (d = 0; d < 4; d++) {

        // ***문제의 부분***. 여기서 조건식에 depth % 3 == 0 && 등을 붙이면 채점 퍼센티지가 달라지고,
        // depth % 3 == 1 && d == lastDirection 로 했을 때 정답이 되었음.
		if (d == lastDirection) {
			continue;
		}

        
        
        // d가 0~3일 때 각각 위, 오른쪽, 아래, 왼쪽.
		if (d == 0) {
			for (i = 0; i < n; i++) {
				k = 0; // k는 숫자를 기록할 곳에 대한 포인터, j는 읽을 곳에 대한 포인터
				for (j = 0; j < n; j++) {
					if (board[depth - 1][j][i] != 0) {
						if (t == 0 && k > 0 && board[depth][k - 1][i] == board[depth - 1][j][i]) {
                            // 직전에 블럭이 합쳐지지 않았고, 직전의 블럭과 다음의 블럭이 같다면 합친다.
							board[depth][k - 1][i] <<= 1;
							t = 1; // t는 직전에 블럭이 합쳐졌는지의 여부
						} else {
							board[depth][k++][i] = board[depth - 1][j][i];
							t = 0;
						}
					}
				}
				while (k < n) { // 아직 남은 부분에 0으로 채우기
					board[depth][k][i] = 0;
					k++;
				}
			}
		} else if (d == 1) {
			for (i = 0; i < n; i++) {
				k = n - 1;
				for (j = n - 1; j >= 0; j--) {
					if (board[depth - 1][i][j] != 0) {
						if (t == 0 && k < n - 1 && board[depth][i][k + 1] == board[depth - 1][i][j]) {
							board[depth][i][k + 1] <<= 1;
							t = 1;
						} else {
							board[depth][i][k--] = board[depth - 1][i][j];
							t = 0;
						}
					}
				}
				while (k >= 0) {
					board[depth][i][k] = 0;
					k--;
				}
			}
		} else if (d == 2) {
			for (i = 0; i < n; i++) {
				k = n - 1;
				for (j = n - 1; j >= 0; j--) {
					if (board[depth - 1][j][i] != 0) {
						if (t == 0 && k < n - 1 && board[depth][k + 1][i] == board[depth - 1][j][i]) {
							board[depth][k + 1][i] <<= 1;
							t = 1;
						} else {
							board[depth][k--][i] = board[depth - 1][j][i];
							t = 0;
						}
					}
				}
				while (k >= 0) {
					board[depth][k][i] = 0;
					k--;
				}
			}
		} else {
			for (i = 0; i < n; i++) {
				k = 0;
				for (j = 0; j < n; j++) {
					if (board[depth - 1][i][j] != 0) {
						if (t == 0 && k > 0 && board[depth][i][k - 1] == board[depth - 1][i][j]) {
							board[depth][i][k - 1] <<= 1;
							t = 1;
						} else {
							board[depth][i][k++] = board[depth - 1][i][j];
							t = 0;
						}
					}
				}
				while (k < n) {
					board[depth][i][k] = 0;
					k++;
				}
			}
		}

        // 현재의 방향(d) 값을 넘깁니다.
		recurse(depth + 1, d);

	}

}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int i, j;

	cin >> n;

    // 입력부
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			cin >> board[0][i][j];
		}
	}

    // 인자는 각각 depth와 direction 값.
    // 진입 시 direction 값은 4인데, 첫 방향은 0~3의 값이 될 수 있기 때문
	recurse(1, 4);

    // 이 구문은 가장 큰 비트 하나를 남기기 위함임.
	while (maxValue != (maxValue & -maxValue)) {
		maxValue -= (maxValue & -maxValue);
	}

	cout << maxValue;

}

20
64 64 32 16 256 0 32 0 512 0 0 128 0 0 0 128 16 64 16 0
16 16 64 0 0 128 64 0 0 0 8 0 256 0 512 128 32 0 16 32
0 128 0 0 0 32 32 64 0 0 0 0 0 32 16 64 0 16 0 0
0 0 0 128 0 128 512 0 0 32 256 32 64 0 32 0 64 0 0 0
0 0 0 16 0 16 0 0 32 0 32 0 0 0 64 0 64 64 0 64
16 0 64 32 128 64 0 128 16 0 0 0 64 0 0 128 0 64 0 128
0 64 32 64 64 0 0 0 128 0 0 0 512 32 0 64 0 0 64 0
0 0 0 0 0 8 256 0 0 32 0 0 0 0 0 8 128 16 0 64
0 8 0 16 0 0 0 128 0 16 16 0 32 0 0 0 0 64 128 128
0 16 16 32 64 0 64 256 0 16 128 128 0 0 64 0 16 0 0 0
0 0 0 16 0 0 0 0 32 0 8 16 128 64 256 0 32 16 128 0
0 256 16 256 0 16 32 8 128 64 0 32 32 512 0 16 0 8 16 0
64 8 16 0 0 0 0 0 128 64 0 128 0 0 8 0 16 0 0 0
0 0 0 0 32 64 0 8 0 0 32 0 0 0 16 128 256 0 128 0
64 8 0 16 32 0 0 0 8 64 64 0 0 0 0 256 64 0 16 0
0 0 32 0 32 32 8 0 0 0 64 0 32 0 0 16 64 128 0 32
0 0 8 64 0 64 0 0 128 64 64 0 0 0 0 32 128 0 128 16
0 0 0 0 32 0 0 32 32 0 16 0 128 0 0 0 0 256 0 32
16 256 0 64 0 16 0 64 0 32 64 32 0 0 0 64 32 64 0 0
16 8 0 32 64 256 0 0 0 128 8 0 32 0 64 0 0 0 64 128
answer: 4096
output: 2048

디버깅 한참 걸리겠네요 흑흑

clrmt 4년 전 1

아 직전 방향을 탐색하지 않는게 문제가 되는군요. 착각했습니다.

EASY버전에 제출한 것도 같은 오류가 있는데 데이터를 추가해야할 수도 있겠습니다.

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

문제

문제

출처

ICPC

틀렸는데 맞았다고 뜨는 것 같습니다.

clrmt 4년 전 0

clrmt 4년 전 4

clrmt 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말