글 읽기 - 게시판에 있는 TC 통틀어 1개의 반례를 찾은 것 같습니다..

lswoo3021 5년 전 2

게시판 모든페이지를 뒤지며 ㅠㅡㅠ TC를 수행해봤는데 이제는 전부다 맞고 아래 한가지만

오류가 있네요 ...물론 논리적인 오류가 있을 것 같긴한데 ㅠㅡㅠ 하루종일해도 못찾고있네요 ..

모두 통과한 것을 확인 한 것은 아래 링크의 TC들입니다.

https://www.acmicpc.net/board/...

현재까지 유일한 반례는 아래인데요 ... 같이 도와주실분이 있다면 정말 감사하겠습니다..

하 ...그나저나 너무 고되네요 ... 왜이렇게 해도해도 늘지않을까요 ㅠ

10
16 16 8 32 32 0 0 8 8 8
16 0 0 0 0 8 0 0 0 16
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

result : 64
- correct : 128
입니다...

#include <iostream>
#include <algorithm>
#include <queue>

#define MAX_SIZE 21

using namespace std;

int n;
int map[MAX_SIZE][MAX_SIZE];
int maxValue = 0;

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

void showMap(int map[][MAX_SIZE]) {
	cout << endl << "map is below" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
}

void move(int dir, int idx, int tMap[][MAX_SIZE]) {
	int cx, cy;
	int mergeFlag[MAX_SIZE];
	if (dir == 1) {	// 상
		for (int i = 0; i < n; i++) {
			cx = i;
			if (tMap[i][idx] != 0) {	// 숫자를 만나면
				for (int j = i - 1; j >= 0; j--) {
					if (tMap[j][idx] != 0) {	// 0이 아닐때
												// 같은 숫자 만나면
						if (tMap[j][idx] == tMap[i][idx]) {
							if (mergeFlag[j] == 1) break;
							tMap[j][idx] = 2 * tMap[j][idx];	// 합치기
							tMap[i][idx] = 0;	// 기존칸 0처리
							mergeFlag[j] = 1;	// 합침 수행 표시
						}
						break;
					}
					cx = j;
				}
				if (cx != i) {
					tMap[cx][idx] = tMap[i][idx];
					tMap[i][idx] = 0;	// 0인 경우 위로 이동처리
				}
			}
		}
	}
	if (dir == 2) {	// 우
		for (int i = n; i >= 0; i--) {
			cy = i;
			if (tMap[idx][i] != 0) {	// 숫자를 만나면
				for (int j = i + 1; j < n; j++) {
					if (tMap[idx][j] != 0) {	// 0이 아닐때
												// 같은 숫자 만나면
						if (tMap[idx][j] == tMap[idx][i]) {
							if (mergeFlag[j] == 1) break;
							tMap[idx][j] = 2 * tMap[idx][j];	// 합치기
							tMap[idx][i] = 0;	// 기존칸 0처리
							mergeFlag[j] = 1;	// 합침 수행 표시
						}
						break;
					}
					cy = j;
				}
				if (cy != i) {
					tMap[idx][cy] = tMap[idx][i];
					tMap[idx][i] = 0;	// 0인 경우 위로 이동처리
				}
			}
		}
	}
	if (dir == 3) {	// 하
		for (int i = n - 1; i >= 0; i--) {
			cx = i;
			if (tMap[i][idx] != 0) {	// 숫자를 만나면
				for (int j = i + 1; j < n; j++) {
					if (tMap[j][idx] != 0) {	// 0이 아닐때
												// 같은 숫자 만나면
						if (tMap[j][idx] == tMap[i][idx]) {
							if (mergeFlag[j] == 1) break;
							tMap[j][idx] = 2 * tMap[j][idx];	// 합치기
							tMap[i][idx] = 0;	// 기존칸 0처리
							mergeFlag[j] = 1;	// 합침 수행 표시
						}
						break;
					}
					cx = j;
				}
				if (cx != i) {
					tMap[cx][idx] = tMap[i][idx];
					tMap[i][idx] = 0;	// 0인 경우 위로 이동처리
				}
			}
		}
	}
	if (dir == 4) {	// 좌
		for (int i = 0; i < n; i++) {
			cy = i;
			if (tMap[idx][i] != 0) {	// 숫자를 만나면
				for (int j = i - 1; j >= 0; j--) {
					if (tMap[idx][j] != 0) {	// 0이 아닐때
												// 같은 숫자 만나면
						if (tMap[idx][j] == tMap[idx][i]) {
							if (mergeFlag[j] == 1) break;
							tMap[idx][j] = 2 * tMap[idx][j];	// 합치기
							tMap[idx][i] = 0;	// 기존칸 0처리
							mergeFlag[j] = 1;	// 합침 수행 표시
						}
						break;
					}
					cy = j;
				}
				if (cy != i) {
					tMap[idx][cy] = tMap[idx][i];
					tMap[idx][i] = 0;	// 0인 경우 위로 이동처리
				}
			}
		}
	}


}
void copyMap(int a[][MAX_SIZE], int b[][MAX_SIZE]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			b[i][j] = a[i][j];
		}
	}
}
int getScore(int tMap[][MAX_SIZE]) {
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			tmp = max(tMap[i][j], tmp);
		}
	}
	return tmp;
}

void dfs(int d, int tMap[MAX_SIZE][MAX_SIZE]) {
	if (d >= 6) return;
	int tmp_map[MAX_SIZE][MAX_SIZE];
	copyMap(tMap, tmp_map);
	for (int i = 1; i < 5; i++) {	// 상 우 좌 하 모두 반복
		for (int j = 0; j < n; j++) {
			move(i, j, tmp_map);	// n 열 또는 행에 대해 이동 1회 수행
		}
		if (d == 5 ) {	// 5회 수행
			maxValue = max(getScore(tmp_map), maxValue);
			//showMap(tmp_map);
			copyMap(tMap, tmp_map);	// 백트래킹
		}
		dfs(d + 1, tmp_map);	// 다음 이동 호출
		copyMap(tMap, tmp_map);	// 백트래킹
	}
}

int main() {

	getInput();
	dfs(1, map);

	/*
	for (int j = 0; j < n; j++) {
	move(4, j, map);
	}
	showMap(map);
	for (int j = 0; j < n; j++) {
	move(3, j, map);
	}
	showMap(map);
	for (int j = 0; j < n; j++) {
	move(2, j, map);
	}
	showMap(map);

	for (int j = 0; j < n; j++) {
	move(1, j, map);
	}
	showMap(map);
	for (int j = 0; j < n; j++) {
	move(2, j, map);
	}
	showMap(map);
	*/


	cout << maxValue << endl;

	int wait;
	cin >> wait;
	return 0;
}

djm03178 5년 전 1

매우 작은 케이스로 반례를 드립니다.

3
8 512 0
128 0 64
512 2 2
output: 512
correct answer: 1024

3
0 64 512
0 256 256
0 0 0
output: 512
correct answer: 1024

3
0 16 0
16 512 0
512 256 1024
output: 1024
correct answer: 2048

lswoo3021 5년 전 0

음.. ㅠㅡㅠ 엇... 제가 소스코드를 잘못올렸으려나요 ㅠㅡㅠ

주신 테스트케이스 3개 모두 correct answer로 잘나와서 다시한번 확인 해주시면 감사하겠습니다!

#include <iostream>
#include <algorithm>
#include <queue>

#define MAX_SIZE 21

using namespace std;

int n;
int map[MAX_SIZE][MAX_SIZE];
int maxValue = 0;

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

void showMap(int map[][MAX_SIZE]) {
	cout << endl << "map is below" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
}

void move(int dir, int idx, int tMap[][MAX_SIZE]) {
	int cx, cy;
	int mergeFlag[MAX_SIZE];
	if (dir == 1) {	// 상
		for (int i = 0; i < n; i++) {
			cx = i;
			if (tMap[i][idx] != 0) {	// 숫자를 만나면
				for (int j = i - 1; j >= 0; j--) {
					if (tMap[j][idx] != 0) {	// 0이 아닐때
												// 같은 숫자 만나면
						if (tMap[j][idx] == tMap[i][idx]) {
							if (mergeFlag[j] == 1) break;
							tMap[j][idx] = 2 * tMap[j][idx];	// 합치기
							tMap[i][idx] = 0;	// 기존칸 0처리
							mergeFlag[j] = 1;	// 합침 수행 표시
						}
						break;
					}
					cx = j;
				}
				if (cx != i) {
					tMap[cx][idx] = tMap[i][idx];
					tMap[i][idx] = 0;	// 0인 경우 위로 이동처리
				}
			}
		}
	}
	if (dir == 2) {	// 우
		for (int i = n; i >= 0; i--) {
			cy = i;
			if (tMap[idx][i] != 0) {	// 숫자를 만나면
				for (int j = i + 1; j < n; j++) {
					if (tMap[idx][j] != 0) {	// 0이 아닐때
												// 같은 숫자 만나면
						if (tMap[idx][j] == tMap[idx][i]) {
							if (mergeFlag[j] == 1) break;
							tMap[idx][j] = 2 * tMap[idx][j];	// 합치기
							tMap[idx][i] = 0;	// 기존칸 0처리
							mergeFlag[j] = 1;	// 합침 수행 표시
						}
						break;
					}
					cy = j;
				}
				if (cy != i) {
					tMap[idx][cy] = tMap[idx][i];
					tMap[idx][i] = 0;	// 0인 경우 위로 이동처리
				}
			}
		}
	}
	if (dir == 3) {	// 하
		for (int i = n - 1; i >= 0; i--) {
			cx = i;
			if (tMap[i][idx] != 0) {	// 숫자를 만나면
				for (int j = i + 1; j < n; j++) {
					if (tMap[j][idx] != 0) {	// 0이 아닐때
												// 같은 숫자 만나면
						if (tMap[j][idx] == tMap[i][idx]) {
							if (mergeFlag[j] == 1) break;
							tMap[j][idx] = 2 * tMap[j][idx];	// 합치기
							tMap[i][idx] = 0;	// 기존칸 0처리
							mergeFlag[j] = 1;	// 합침 수행 표시
						}
						break;
					}
					cx = j;
				}
				if (cx != i) {
					tMap[cx][idx] = tMap[i][idx];
					tMap[i][idx] = 0;	// 0인 경우 위로 이동처리
				}
			}
		}
	}
	if (dir == 4) {	// 좌
		for (int i = 0; i < n; i++) {
			cy = i;
			if (tMap[idx][i] != 0) {	// 숫자를 만나면
				for (int j = i - 1; j >= 0; j--) {
					if (tMap[idx][j] != 0) {	// 0이 아닐때
												// 같은 숫자 만나면
						if (tMap[idx][j] == tMap[idx][i]) {
							if (mergeFlag[j] == 1) break;
							tMap[idx][j] = 2 * tMap[idx][j];	// 합치기
							tMap[idx][i] = 0;	// 기존칸 0처리
							mergeFlag[j] = 1;	// 합침 수행 표시
						}
						break;
					}
					cy = j;
				}
				if (cy != i) {
					tMap[idx][cy] = tMap[idx][i];
					tMap[idx][i] = 0;	// 0인 경우 위로 이동처리
				}
			}
		}
	}


}
void copyMap(int a[][MAX_SIZE], int b[][MAX_SIZE]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			b[i][j] = a[i][j];
		}
	}
}
int getScore(int tMap[][MAX_SIZE]) {
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			tmp = max(tMap[i][j], tmp);
		}
	}
	return tmp;
}

void dfs(int d, int tMap[MAX_SIZE][MAX_SIZE]) {
	if (d >= 6) return;
	int tmp_map[MAX_SIZE][MAX_SIZE];
	copyMap(tMap, tmp_map);
	for (int i = 1; i < 5; i++) {	// 상 우 좌 하 모두 반복
		for (int j = 0; j < n; j++) {
			move(i, j, tmp_map);	// n 열 또는 행에 대해 이동 1회 수행
		}
		if (d == 5 ) {	// 5회 수행
			maxValue = max(getScore(tmp_map), maxValue);
			//showMap(tmp_map);
			copyMap(tMap, tmp_map);	// 백트래킹
		}
		dfs(d + 1, tmp_map);	// 다음 이동 호출
		copyMap(tMap, tmp_map);	// 백트래킹
	}
}

int main() {

	getInput();
	dfs(1, map);

	/*
	for (int j = 0; j < n; j++) {
	move(4, j, map);
	}
	showMap(map);
	for (int j = 0; j < n; j++) {
	move(3, j, map);
	}
	showMap(map);
	for (int j = 0; j < n; j++) {
	move(2, j, map);
	}
	showMap(map);

	for (int j = 0; j < n; j++) {
	move(1, j, map);
	}
	showMap(map);
	for (int j = 0; j < n; j++) {
	move(2, j, map);
	}
	showMap(map);
	*/


	cout << maxValue << endl;

	int wait;
	cin >> wait;
	return 0;
}

jh05013 5년 전 3

훨씬 간단한 반례를 드립니다.

2
4 2
2 0

songjuh 5년 전 1

ㅠㅠㅠㅠㅠ 저랑 같은 처지 시군요.. 같이 힘내요 우리 제가 이유 찾으면 꼭! 알려드릴께요! ㅠㅠㅠㅠ

djm03178 5년 전 1

저는 이것도 틀리게 나옵니다. 그렇다면 의심해볼 건 배열의 범위를 벗어나는 게 있거나, 초기화되지 않은 변수를 사용했을 가능성이 있겠네요.

lswoo3021 5년 전 0

@jh05013 엇 ... 정답이 8 아닌가욥 ?! 해당케이스는 원래 잘 나오는 것 같네요ㅜ

jh05013 5년 전 1

몇 분 사이에 댓글이 많이 달려서...

djm님 답변대로 undefined behavior(정의되지 않은 동작)이 있는지 확인해 보시면 되겠습니다.

djm03178 5년 전 1

일단 한가지 잘못된 곳은 60번째 줄에서 i=n부터 시작하고 있는 것입니다. 이는 84번째 줄에서 n-1부터 시작하고 있는 것과 대조됩니다.

하지만 이걸로는 아직 제 컴퓨터에서 정답이 안 나옵니다. 그렇지만 초기화 되지 않은 곳에 접근하는 것은 맞는 것 같습니다. 왜냐하면, 153번째 줄에서 tmp_map을 0으로 초기화해주면 제 컴퓨터에서도 제가 제시한 예시들에 대해 정답이 나오기 때문입니다.

그래도 제출하면 여전히 틀리는데, 여기서부터는 더 알아봐야 할 것 같습니다.

djm03178 5년 전 1

혹시 그것들을 고치고 나서 아래 예시도 잘 나오는지 확인해 보세요.

3
4 512 2
512 2 64
4 8 64
output: 512
correct answer: 1024

3
64 2 128
8 0 0
64 2 8
output: 128
correct answer: 256

3
1024 32 512
0 256 128
128 0 0
output: 1024
correct answer: 2048

lswoo3021 5년 전 0

항상 도움주시는 @djm03178 님 그리고 도움주신

@jh05013 님 @songjuh 님 감사합니다~

이번거는 ..ㅋㅋ 생각보다 복잡해서 ㅠㅡㅠ 나중에 좀더 고민해보겠습니다 ㅠㅡㅠ

같은 소스코드를 가지고도 다른결과가 나오나보네요.

말씀하신대로 변수 초기화, 정의되지 않은 동작, 인덱스 영역 초과 같은 문제가 있지 않을까 싶네요 ..

제가 사용하는 것은 visualstudio 2017버전이고... 컴파일러 버전까진 잘 모르겠네요 아무쪼록

감사합니다 :)

hacoon 5년 전 4

올려주신 케이스의 정답이 64가 맞는거같습니다.

제코드도 64나오는데 정답처리됐어요

8 8 4 16 32 0 0 8 8 8

8 8 4 0 0 8 0 0 0 0

16 0 0 16 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 16

0 0 0 0 0 0 0 0 0 2

wrong = 64

correct = 128

혹시 이 tc랑 헷갈리신게 아닌지?

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

문제

문제

출처

ICPC

게시판에 있는 TC 통틀어 1개의 반례를 찾은 것 같습니다..

lswoo3021 5년 전 2

djm03178 5년 전 1

lswoo3021 5년 전 0

jh05013 5년 전 3

songjuh 5년 전 1

djm03178 5년 전 1

lswoo3021 5년 전 0

jh05013 5년 전 1

djm03178 5년 전 1

djm03178 5년 전 1

lswoo3021 5년 전 0

hacoon 5년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말