글 읽기 - 인터넷 검색가능한 테케 다 맞는데 왜 틀리다 뜨는지...??

codbs017 5년 전 0

이 이유를 찾아주신 다면 당신은 코딩의 신...

#include <algorithm>
#include <iostream>
#include <deque>
#include <fstream>
using namespace std;
int N;
int ans = 0;
int maxsearch(int** map) {
	int i, j;
	int maxi = 0;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			maxi = max(maxi, map[i][j]);
		}
	}
	return maxi;
}
int** copymap(int**map) {
	int** origin= new int*[N];
	for (int i = 0; i < N; i++) {
		origin[i]= new int[N];
		for (int j = 0; j < N; j++) {
			origin[i][j] = map[i][j];
		}
	}
	return origin;
}
void pushbutton(int buttontype, int** map) {
	deque<int> deq;
	int x, y=0;
	int a, b;
	if (buttontype == 0) {
		for (x = 0; x < N; x++) {
			for (y = 0; y < N; y++) {
				//가로 한 줄의 애들의 정보를 다 모음 0제외
				if (map[x][y] > 0) {					
					deq.push_back(map[x][y]);
					map[x][y] = 0;//모으며 지도를 다0으로 초기화 시켜줌
				}
			}
			y = 0;
			while (deq.size()>1) {//큐에 넣은 것 중에 같은것이 연속으로 있는 것만 더해서 지도에 넣어줌
                //두개씩 뽑아서
				a = deq.front();
				deq.pop_front();
				b = deq.front();
				
				
				if (a == b) {
					map[x][y] = a + b;
					deq.pop_front();
					y++;
				}
				else {//같지 않다면 a만 뽑고 b는 남겨둠
					map[x][y] = a;					
					y++;
					
				}
			}
			if (deq.size() == 1) {//큐에 남은 거 있다면 넣어주기
				map[x][y] = deq.front();				
				deq.pop_front();
			}
		}
		
	}
	else if (buttontype == 1) {
		for (x = 0; x < N; x++) {
			for (y = 0; y < N; y++) {
				
				if (map[x][y] > 0) {
					deq.push_back(map[x][y]);
					map[x][y] = 0;
				}
			}
			y = N - 1;
			while (deq.size()>1) {
				a = deq.back();
				deq.pop_back();
				b = deq.back();
				if (a == b) {
					map[x][y] = a + b;
					deq.pop_back();
					y--;
				}
				else {
					map[x][y] = a;
	
					y--;
					
				}
			}
			if (deq.size() == 1) {
				map[x][y] = deq.back();
				deq.pop_back();
			}
		}
	}
	else if (buttontype == 2) {
		for (y = 0; y < N; y++) {
			for (x = 0; x < N; x++) {
				
				if (map[x][y] > 0) {
					deq.push_back(map[x][y]);
					map[x][y] = 0;
					
				}
			}
			x = 0;
			while (deq.size()>1) {
				a = deq.front();
				deq.pop_front();
				b = deq.front();
				
				if (a == b) {
					map[x][y] = a + b;
					deq.pop_front();
					x++;
					
				}
				else {
					map[x][y] = a;
					x++;
					
				}
			}
			if (deq.size() == 1) {
				map[x][y] = deq.front();
			
				deq.pop_front();
			}
		}
	}
	else {
		for (y = 0; y < N; y++) {
			for (x = 0; x < N; x++) {
		
				if (map[x][y] > 0) {
					deq.push_back(map[x][y]);
					map[x][y] = 0;
				}
			}
			x = N - 1;
			while (deq.size()>1) {
				a = deq.back();
				deq.pop_back();
				b = deq.back();
				
				if (a == b) {
					map[x][y] = a + b;
					b = deq.back();
				}
				else {
					map[x][y] = a;
					x--;
					
				}
			}
			if (deq.size() == 1) {
				map[x][y] = deq.back();
				deq.pop_back();
			}
		}
	}
}
int play(int** map, int count) {//재귀 돌려서 버튼 4개를 5개씩 조합해서 하는 완전탐색
	int i;
	int** origin=NULL;
	if (count == 5) {
		int maxi = maxsearch(map);
		return maxi;
	}
	
		for (i = 0; i < 4; i++) {
		origin= copymap(map);
		//push button
		pushbutton(i, map);
		ans = max(ans, play(map, count+1));
		
		map = origin;	//button 원상 복귀
	
		}
	
	return ans;
}
int main() {
	//ifstream fin("input.txt");
	cin >> N;
	int i, j;
	int** map = new int*[N];
	for (i = 0; i < N;i++) {
		map[i] = new int[N];
		for (j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	
	play(map, 0);
	cout << ans<<endl;
	//system("pause");
	return 0;
}

djm03178 5년 전 3

이유까지는 모르겠지만, 최대한 작은 케이스에서 반례를 찾아드립니다.

3
16 2 256
2 64 256
256 256 32
output: 512
correct answer: 1024

3
32 32 256
16 64 256
128 128 128
output: 512
correct answer: 1024

3
0 0 256
256 512 4
8 1024 0
output: 1024
correct answer: 2048

gggkth 5년 전 0

@djm03178

혹시 두번째 케이스에서 1024가 어떻게 나오는 건지 알려주실 수 있나요?

모든 케이스 조사하게 짰는데 512밖에 안 나오는 거 같아서요ㅜㅜ

djm03178 5년 전 1

이렇게 하면 되지 않을까요?

gggkth 5년 전 0

@djm03178

앗 감사합니다! 덕분에 잘못된 부분을 찾았어요 4방향 돌리는걸 4가 아니라 N으로 하고 있었네요.. 이런 어이없는 실수를 ㅜㅜㅜ

감사합니다 ㅎㅎ

bibiair 5년 전 0

3
16 2 256
2 64 256
256 256 32
output: 512
correct answer: 1024

혹시 이케이스는 어떻게 답이 나오는 건가요??

djm03178 5년 전 0

이렇게 하면 됩니다.

bibiair 5년 전 0

감사합니다! 덕분에 맞았네요!

lswoo3021 5년 전 0

@djm03178 안녕하세요 !! ㅠㅡㅠ 혹시 제시해주셨던

0 0 256

256 512 4

8 1024 0

에 대한 값이 2048로 말씀해주셨는데 ㅠㅡㅠ

어떻게 가능한것인지 알려주실수 있을까요 ㅠㅡㅠ

거의 모든케이스 다해봤는데 이것만 답이틀려서요 ㅠ

djm03178 5년 전 0

이렇게 하면 됩니다.

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

문제

문제

출처

ICPC

인터넷 검색가능한 테케 다 맞는데 왜 틀리다 뜨는지...??

codbs017 5년 전 0

djm03178 5년 전 3

gggkth 5년 전 0

djm03178 5년 전 1

gggkth 5년 전 0

bibiair 5년 전 0

djm03178 5년 전 0

bibiair 5년 전 0

lswoo3021 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말