글 읽기 - 반례는 찾았는데 문제점을 모르겠습니다..

pch1623 4년 전 0

반례는

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

이거인데 문제는 제가 재귀로 구현을 했는데 재귀함수 내에서 up,down,left,right 순서를 바꿔주면 답이나와요 근데그럼 다른 예제에서 오답이나오더라구요.. 재귀함수 안쪽 부분이 잘못된거 같은데 아무리 찾아봐도 잘 모르곘어서 질문남깁니다 ㅠㅠ

#include<iostream>
#include<algorithm>
using namespace std;



int N;
int arr[21][21];
int new_map[21][21];
int ans[21][21];
int result = 0;
void left(int map[][21]) {//왼쪽으로 미는 함수

	for (int i = 0; i < N; i++) {
		int num = 0;
		int idx = 0;
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0)continue;
			else {
				if (num == 0)num = map[i][j];
				else {
					if (num == map[i][j]) {
						new_map[i][idx++] = num * 2;
						num = 0;
					}
					else {
						new_map[i][idx++] = num;
						num = map[i][j];
					}
				}
			}
		}
		if (num != 0) new_map[i][idx] = num;
	}
	for (int i = 0; i < N; i++) {// new_map 을 ans로 넣어주고 new map은 0으로 초기화
		for (int j = 0; j < N; j++) {
			ans[i][j] = new_map[i][j];
			new_map[i][j] = 0;
		}
	}

}
void right(int map[][21]) {//오른쪽으로 미는 함수

	for (int i = 0; i < N; i++) {
		int num = 0;
		int idx = N - 1;
		for (int j = N - 1; j >= 0; j--) {
			if (map[i][j] == 0)continue;
			else {
				if (num == 0)num = map[i][j];
				else {
					if (num == map[i][j]) {
						new_map[i][idx--] = num * 2;
						num = 0;
					}
					else {
						new_map[i][idx--] = num;
						num = map[i][j];
					}
				}
			}
		}
		if (num != 0) new_map[i][idx] = num;
	}
	for (int i = 0; i < N; i++) {// new_map 을 ans로 넣어주고 new map은 0으로 초기화
		for (int j = 0; j < N; j++) {
			ans[i][j] = new_map[i][j];
			new_map[i][j] = 0;
		}
	}
}
void up(int map[][21]) {//위로 올리는 함수

	for (int j = 0; j < N; j++) {
		int num = 0;
		int idx = 0;
		for (int i = 0; i < N; i++) {
			if (map[i][j] == 0)continue;
			else {
				if (num == 0)num = map[i][j];
				else {
					if (num == map[i][j]) {
						new_map[idx++][j] = num * 2;
						num = 0;
					}
					else {
						new_map[idx++][j] = num;
						num = map[i][j];
					}
				}
			}
		}
		if (num != 0) new_map[idx++][j] = num;
	}
	for (int i = 0; i < N; i++) {// new_map 을 ans로 넣어주고 new map은 0으로 초기화
		for (int j = 0; j < N; j++) {
			ans[i][j] = new_map[i][j];
			new_map[i][j] = 0;
		}
	}
}
void down(int map[][21]) {//아래로 내리는 함수

	for (int j = 0; j < N; j++) {
		int num = 0;
		int idx = N - 1;
		for (int i = N - 1; i >= 0; i--) {
			if (map[i][j] == 0)continue;
			else {
				if (num == 0)num = map[i][j];
				else {
					if (num == map[i][j]) {
						new_map[idx--][j] = num * 2;
						num = 0;
					}
					else {
						new_map[idx--][j] = num;
						num = map[i][j];
					}
				}
			}
		}
		if (num != 0) new_map[idx--][j] = num;
	}
	for (int i = 0; i < N; i++) {// new_map 을 ans로 넣어주고 new map은 0으로 초기화
		for (int j = 0; j < N; j++) {
			ans[i][j] = new_map[i][j];
			new_map[i][j] = 0;
		}
	}
}
int check(int map[][21]) {// 배열에서 최대값
	int num = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			num = max(num, map[i][j]);
		}
	}
	return num;
}

void func(int array[][21], int cnt) {//재귀로 구현
	if (cnt == 5) return;//5번까지만
	result = max(result, check(array));


	right(array);
	func(ans, cnt + 1);
	left(array);
	func(ans, cnt + 1);
	up(array);
	func(ans, cnt + 1);
	down(array);
	func(ans, cnt + 1);

}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}
	func(arr, 0);
	cout << result;
}

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

문제

문제

출처

ICPC

반례는 찾았는데 문제점을 모르겠습니다..

pch1623 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말