글 읽기 - 어디서 문제가 발생하는지 감이 안잡힙니다.... c++

jw_ryux 4년 전 0

백트래킹으로 모든 경우를 돌려서 확인을 하는데 반례를 확인은 했는데 왜 다르게 나오는지를 잘 모르겠습니다... 재귀다보니까 보면 볼수록 헷갈리네요 ㅜㅜㅜ 도움 좀 얻고싶습니다 ㅜㅜ

<반례>

0 8 1024

4 0 4

0 1024 32

output: 1024

correct answer: 2048

256 8 128

16 0 256

0 8 0

output: 256

correct answer: 512

#include <iostream>
#include <algorithm>
#include <queue>
#define ll long long
#define pii pair<int, int>

using namespace std;
/*
2048 easy
개요 . 4x4 크기의 보드에서 하는 게임. 내가 생각하는 2048게임과 같지만 이동할때마다 블록이 추가되는 경우는 없는걸로 간주)
보드 크기는 주어진다. NxN 으로 
*/

int board[21][21];
int n; //보드 크기
int max_sum = 0; //최종 합

void dfs(int depth) { 
	if (depth == 5) { //5회 이동 완료
		int sum = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (sum < board[i][j]) {	//판에서 가장 큰 값을 찾는다.
					sum = board[i][j];
				}
			}
		}

		if (max_sum < sum) { //다른 경우의 가장 큰 값들 중에 그 사이에서도 가장 큰 값을 넣는다.
			max_sum = sum;
		}
		return; 
	}

	for (int i = 0; i < 4; i++) { // 4 방향에 대하여, 0 : 상, 1 : 하, 2 : 좌, 3 : 우
		int recover_board[21][21];
		//원래 상태 저장
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				recover_board[j][k] = board[j][k];  //board 내용이 이제 바뀜
			}
		}

		for (int j = 0; j < n; j++) { //각 행(또는 열이 될 수도 있음)에 대해서

			vector<int> temp; // 각 행(또는 열이 될 수도 있음)에 대한 상태 변경을 위한 vector
			for (int k = 0; k < n; k++){ //0은 빼고 push
				if (i < 2) { //열에 대한 작업이라면
					if (board[k][j] != '0') temp.push_back(board[k][j]);
				}
				else {	//행에 대한 작업이라면
					if (board[j][k] != '0') temp.push_back(board[j][k]);
				}
				
			}
			//k번째 행(또는 열)에 대해
			if (i == 1 || i == 3) { //밑으로 내리는 경우나 오른쪽으로 미는 경우 인덱스들을 반대로 해야해서 그냥 뒤집어서 계산
				reverse(temp.begin(), temp.end());
			}
			
			vector<int> new_board;	//temp에 저장된 값들을 합치고 갱신된 값을 저장할 vector

			for (int cur = 0; cur < temp.size()-1; cur++) { //나열된 0이 아닌 값들에 대해 
				if (temp[cur] == temp[cur + 1]) { //다음 값과 같다면
					new_board.push_back(temp[cur] * 2); //x2의 값을 밀어 넣는다.
					cur++; 
				}
				else {	// 다르면
					new_board.push_back(temp[cur]); //그대로 집어넣음
				}
			}

			for (int cur = new_board.size(); cur < n; cur++) {
				new_board.push_back(0);	//n 길이를 맞춰야하기때문에 남은 공간들은 0으로 채움 
			}

			if (i == 1 || i == 3) { // 뒤집은 놈들을 다시 뒤집어야 올바른 값을 전달함
				reverse(new_board.begin(), new_board.end());
			}


			for (int cur = 0; cur < n; cur++) {
				if (i < 2) { //열에 대한 작업이라면
					board[cur][j] = new_board[cur];	//세로로 넣음
				}
				else {	//행에 대한 작업이라면
					board[j][cur] = new_board[cur];		//가로로 넣음
				}
			}
			
		}

		dfs(depth + 1);

		//원래 상태로 복구
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				board[j][k] = recover_board[j][k];
			}
		}
	}
}


int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> n;

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

	dfs(0);

	cout << max_sum << "\n";

	return 0;
}

jw_ryux 4년 전 0

49번 52번줄 .... 비교문을 캐릭터형으로... 하이고... 내 9시간....

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

문제

문제

출처

ICPC

어디서 문제가 발생하는지 감이 안잡힙니다.... c++

jw_ryux 4년 전 0

jw_ryux 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말