글 읽기 - 17% 틀렸다고 나오네요 ㅠㅠ

shwjdgh3842 2년 전 1

발상은 상하좌우로 움직이는 함수를 구현하고 (여러번 테스트 해 봤는데 재대로 작동되는것 같아요..) 백트레킹을 통해 모든 경우에 대해 최대값을 얻어내는 방식입니다.

게시판에 있는 많은 반례들도 잘 통과하는데 도대체 어디서 틀리는지 감이 안오네요..

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <queue>
#include <vector>
#include <string>
using namespace std;
int n;
int board[20][20];
int max_val = 0;

//상하좌우 방향으로 판을 움직인 경우 board 변화
//왼쪽으로 민다-> 수가 같은것을 합친다 -> 다시 왼쪽으로 민다
void moveright() {
	//오른쪽으로 민다.
	for (int i = 0; i < n; i++) {
		for (int j = n - 2; j >= 0; j--) {
			if (board[i][j] != 0 && board[i][j + 1] == 0) {
				int k = j;
				while (k != n-1 && board[i][k] != 0 && board[i][k + 1] == 0) {
					board[i][k + 1] = board[i][k];
					board[i][k] = 0;
					k++;
				}
			}
		}
	}
	//오른쪽 끝줄부터 같은 수가 있으면 더함
	for (int j = n - 1; j > 0; j--) {
		for (int i = 0; i < n; i++) {
			if (board[i][j] == board[i][j - 1]) {
				board[i][j] *= 2;
				board[i][j - 1] = 0;
			}
		}
	}
	//오른쪽으로 민다.
	for (int i = 0; i < n; i++) {
		for (int j = n - 2; j >= 0; j--) {
			if (board[i][j] != 0 && board[i][j + 1] == 0) {
				int k = j;
				while (k != n - 1 && board[i][k] != 0 && board[i][k + 1] == 0) {
					board[i][k + 1] = board[i][k];
					board[i][k] = 0;
					k++;
				}
			}
		}
	}
}
void moveleft() {
	//왼쪽으로 민다.
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n - 1; j++) {
			//옮겨야 하는 상황이라면
			if (board[i][j] != 0 && board[i][j-1] == 0) {
				int k = j;
				while (k!=0 && board[i][k] != 0 && board[i][k-1] == 0) {
					board[i][k - 1] = board[i][k];
					board[i][k] = 0;
					k--;
				}
			}
		}
	}
	//왼쪽 끝줄부터 같은 수가 있으면 더함
	for (int j = 0; j < n - 1; j++) {
		for (int i = 0; i < n; i++) {
			if (board[i][j] == board[i][j + 1]) {
				board[i][j] *= 2;
				board[i][j + 1] = 0;
			}
		}
	}
	//왼쪽으로 민다.
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n; j++) {
			//옮겨야 하는 상황이라면
			if (board[i][j] != 0 && board[i][j - 1] == 0) {
				int k = j;
				while (k != 0 && board[i][k] != 0 && board[i][k - 1] == 0) {
					board[i][k - 1] = board[i][k];
					board[i][k] = 0;
					k--;
				}
			}
		}
	}
}
void moveup() {
	//위쪽으로 민다.
	for (int j = 0; j < n; j++) {
		for (int i = 1; i < n; i++) {
			if (board[i][j] != 0 && board[i - 1][j] == 0) {
				int k = i;
				while (k != 0 && board[k][j] != 0 && board[k - 1][j] == 0) {
					board[k - 1][j] = board[k][j];
					board[k][j] = 0;
					k--;
				}
			}
		}
	}
	//위쪽 끝줄부터 같은 수가 있으면 더함
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] == board[i + 1][j]) {
				board[i][j] *= 2;
				board[i + 1][j] = 0;
			}
		}
	}
	//위쪽으로 민다.
	for (int j = 0; j < n; j++) {
		for (int i = 1; i < n; i++) {
			if (board[i][j] != 0 && board[i - 1][j] == 0) {
				int k = i;
				while (k != 0 && board[k][j] != 0 && board[k - 1][j] == 0) {
					board[k - 1][j] = board[k][j];
					board[k][j] = 0;
					k--;
				}
			}
		}
	}
}
void movedown() {
	//아래쪽으로 민다.
	for (int j = 0; j < n; j++) {
		for (int i = n - 2; i >= 0; i--) {
			if (board[i][j] != 0 && board[i + 1][j] == 0) {
				int k = i;
				while (k != n - 1 && board[k][j] != 0 && board[k + 1][j] == 0) {
					board[k + 1][j] = board[k][j];
					board[k][j] = 0;
					k++;
				}
			}
		}
	}
	//아래쪽 끝줄부터 같은 수가 있으면 더함
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] == board[i - 1][j]) {
				board[i][j] *= 2;
				board[i - 1][j] = 0;
			}
		}
	}
	//아래쪽으로 민다.
	for (int j = 0; j < n; j++) {
		for (int i = n - 2; i >= 0; i--) {
			if (board[i][j] != 0 && board[i + 1][j] == 0) {
				int k = i;
				while (k != n - 1 && board[k][j] != 0 && board[k + 1][j] == 0) {
					board[k + 1][j] = board[k][j];
					board[k][j] = 0;
					k++;
				}
			}
		}
	}
}

void test() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << board[i][j] << ' ';
		}
		cout << endl;
	}
}

//num번 재귀실행하여 최고값을 갱신하는 함수
void fun(int num) {
	//기저사례 : 5번 탐색을 완료한 경우
	if (num == 5) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (max_val < board[i][j]) {
					max_val = board[i][j];
				}
			}
		}
		return;
	}
	//판의 이동을 진행하기 전에 백업
	int copyboard[20][20];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			copyboard[i][j] = board[i][j];
		}
	}
	moveup();
	fun(num + 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			board[i][j] = copyboard[i][j];
		}
	}
	moveleft();
	fun(num + 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			board[i][j] = copyboard[i][j];
		}
	}
	movedown();
	fun(num + 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			board[i][j] = copyboard[i][j];
		}
	}
	moveright();
	fun(num + 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			board[i][j] = copyboard[i][j];
		}
	}

}


int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}
	fun(0);
	//movedown();
	//test();
	cout << max_val;
}

knight7024 2년 전 1

55번째 라인에서 j가 n - 1까지 밖에 안돌고 있습니다.

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

문제

문제

출처

ICPC

17% 틀렸다고 나오네요 ㅠㅠ

shwjdgh3842 2년 전 1

knight7024 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말