글 읽기 - 반례를 알아도 어디가 틀렸는지 모르겠습니다!

akscjsdl 5년 전 1

배열 복사도 제대로 해줬는데 어느 부분이 문제일까요??

[#3]

10
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0
64 64 128 0 0 0 0 0 0 0
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0
64 64 128 0 0 0 0 0 0 0
128 32 2 4 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0

답 : 1024

output: 512

[#2]

7
2 2 2 2 2 2 2
2 0 2 2 2 2 2
2 0 2 2 2 2 2
2 0 2 2 2 2 2
2 2 2 0 2 2 2
2 2 2 2 2 2 0
2 2 2 2 2 2 0

답 : 32

output: 64

#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;

#define MAX 20
int N;
int rst = 0;

//정렬
void arrange(int dir, int map[][MAX]) {
	int idx;
	int tmp[MAX];

	if (dir == 0) {
		for (int j = 0; j < N; j++) {
			idx = 0;
			for (int i = 0; i < N; i++) {
				if (map[i][j] != 0) {
					tmp[idx++] = map[i][j];
					map[i][j] = 0;
				}
			}
			for (int i = 0; i < idx; i++)
				map[i][j] = tmp[i];
		}
	}
	else if (dir == 1) {
		for (int i = 0; i < N; i++) {
			idx = 0;
			for (int j = N - 1; j >= 0; j--) {
				if (map[i][j] != 0) {
					tmp[idx++] = map[i][j];
					map[i][j] = 0;
				}
			}
			for (int j = N - 1; j >= N - idx; j--)
				map[i][j] = tmp[(N - 1) - j];
		}
	}
	else if (dir == 2) {
		for (int j = 0; j < N; j++) {
			idx = 0;
			for (int i = N - 1; i >= 0; i--) {
				if (map[i][j] != 0) {
					tmp[idx++] = map[i][j];
					map[i][j] = 0;
				}
			}
			for (int i = N - 1; i >= N - idx; i--)
				map[i][j] = tmp[(N - 1) - i];
		}
	}
	else if (dir == 3) {
		for (int i = 0; i < N; i++) {
			idx = 0;
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0) {
					tmp[idx++] = map[i][j];
					map[i][j] = 0;
				}
			}
			for (int j = 0; j < idx; j++)
				map[i][j] = tmp[j];
		}
	}
}

void tilt_v(int dir, int row, int map[][MAX]) {
	int ny;
	int y = row;

	if (dir == 0) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 0)continue;

			ny = y - 1;
			while (map[ny][x] == 0)
				ny -= 1;
			if (ny < 0)continue;
			if (map[ny][x] == map[y][x]) {
				map[y][x] = 0;
				map[ny][x] *= 2;
			}
		}
	}
	else if (dir == 2) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 0)continue;

			ny = y + 1;
			while (map[ny][x] == 0)
				ny += 1;
			if (ny >= N)continue;
			if (map[ny][x] == map[y][x]) {
				map[y][x] = 0;
				map[ny][x] *= 2;
			}
		}
	}
}

void tilt_h(int dir, int col, int map[][MAX]) {
	int nx;
	int x = col;

	if (dir == 3) {
		for (int y = 0; y < N; y++) {
			if (map[y][x] == 0)continue;

			nx = x - 1;
			while (map[y][nx] == 0)
				nx -= 1;
			if (nx < 0)continue;
			if (map[y][nx] == map[y][x]) {
				map[y][x] = 0;
				map[y][nx] *= 2;
			}
		}
	}
	else if (dir == 1) {
		for (int y = 0; y < N; y++) {
			if (map[y][x] == 0)continue;

			nx = x + 1;
			while (map[y][nx] == 0)
				nx += 1;
			if (nx >= N)continue;
			if (map[y][nx] == map[y][x]) {
				map[y][x] = 0;
				map[y][nx] *= 2;
			}
		}
	}
}

void dfs(int cnt, int m[][MAX]) {
	if (cnt >= 5) {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				rst = max(rst, m[i][j]);
		return;
	}

	int tmp[MAX][MAX];
	memcpy(tmp, m, sizeof(tmp));


	//0: 북, 1: 동, 2: 남, 3: 서
	//북
	for (int i = N - 1; i > 1; i--)
		tilt_v(0, i, m);
	arrange(0, m);
	dfs(cnt + 1, m);
	memcpy(m, tmp, sizeof(tmp));


	//동
	for (int i = 0; i < N-1; i++)
		tilt_h(1, i, m);
	arrange(1,m);
	dfs(cnt + 1,m);

	memcpy(m, tmp, sizeof(tmp));

	//남
	for (int i = 0; i < N-1; i++)
		tilt_v(2, i,m);
	arrange(2,m);
	dfs(cnt + 1,m);

	memcpy(m, tmp, sizeof(tmp));

	//서
	for (int i = N - 1; i > 1; i--)
		tilt_h(3, i,m);
	arrange(3,m);
	dfs(cnt + 1,m);

	memcpy(m, tmp, sizeof(tmp));
}

int main() {
	int map[MAX][MAX];
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	dfs(0, map);
	cout << rst << endl;
	return 0;
}

akscjsdl 5년 전 0

해결했습니다...ㅎㅎ

한 행 또는 열에서 한 블록은 한 번만 합쳐질 수 있는데 여러 번 합치게 해놨었네요

visited라는 bool 배열을 이용해서 한 번 수행한 블록에 표시하고, 그 다음 블록이랑 합치지 못 하게 했습니다.

#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;

#define MAX 20
int N;
int rst = 0;
bool visited[MAX][MAX];

//정렬
void arrange(int dir, int map[][MAX]) {
	int idx;
	int tmp[MAX];

	if (dir == 0) {
		for (int j = 0; j < N; j++) {
			idx = 0;
			for (int i = 0; i < N; i++) {
				if (map[i][j] != 0) {
					tmp[idx++] = map[i][j];
					map[i][j] = 0;
				}
			}
			for (int i = 0; i < idx; i++)
				map[i][j] = tmp[i];
		}
	}
	else if (dir == 1) {
		for (int i = 0; i < N; i++) {
			idx = 0;
			for (int j = N - 1; j >= 0; j--) {
				if (map[i][j] != 0) {
					tmp[idx++] = map[i][j];
					map[i][j] = 0;
				}
			}
			for (int j = N - 1; j >= N - idx; j--)
				map[i][j] = tmp[(N - 1) - j];
		}
	}
	else if (dir == 2) {
		for (int j = 0; j < N; j++) {
			idx = 0;
			for (int i = N - 1; i >= 0; i--) {
				if (map[i][j] != 0) {
					tmp[idx++] = map[i][j];
					map[i][j] = 0;
				}
			}
			for (int i = N - 1; i >= N - idx; i--)
				map[i][j] = tmp[(N - 1) - i];
		}
	}
	else if (dir == 3) {
		for (int i = 0; i < N; i++) {
			idx = 0;
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0) {
					tmp[idx++] = map[i][j];
					map[i][j] = 0;
				}
			}
			for (int j = 0; j < idx; j++)
				map[i][j] = tmp[j];
		}
	}
}

void tilt_v(int dir, int row, int map[][MAX]) {
	int ny;
	int y = row;

	if (dir == 0) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 0)continue;

			ny = y - 1;
			while (map[ny][x] == 0)
				ny -= 1;
			if (ny < 0)continue;
			if (map[ny][x] == map[y][x] && !visited[ny][x]) {
				map[y][x] = 0;
				map[ny][x] *= 2;
				visited[ny][x] = true;
			}
		}
	}
	else if (dir == 2) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 0)continue;

			ny = y + 1;
			while (map[ny][x] == 0)
				ny += 1;
			if (ny >= N)continue;
			if (map[ny][x] == map[y][x] && !visited[ny][x]) {
				map[y][x] = 0;
				map[ny][x] *= 2;
				visited[ny][x] = true;
			}
		}
	}
}

void tilt_h(int dir, int col, int map[][MAX]) {
	int nx;
	int x = col;

	if (dir == 3) {
		for (int y = 0; y < N; y++) {
			if (map[y][x] == 0)continue;

			nx = x - 1;
			while (map[y][nx] == 0)
				nx -= 1;
			if (nx < 0)continue;
			if (map[y][nx] == map[y][x] && !visited[y][nx]) {
				map[y][x] = 0;
				map[y][nx] *= 2;
				visited[y][nx] = true;
			}
		}
	}
	else if (dir == 1) {
		for (int y = 0; y < N; y++) {
			if (map[y][x] == 0)continue;

			nx = x + 1;
			while (map[y][nx] == 0)
				nx += 1;
			if (nx >= N)continue;
			if (map[y][nx] == map[y][x] && !visited[y][nx]) {
				map[y][x] = 0;
				map[y][nx] *= 2;
				visited[y][nx] = true;
			}
		}
	}
}

void dfs(int cnt, int m[][MAX]) {
	if (cnt >= 5) {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				rst = max(rst, m[i][j]);
		return;
	}

	int tmp[MAX][MAX];
	memcpy(tmp, m, sizeof(tmp));

	/*if (cnt == 1) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				printf("%4d", m[i][j]);
			}
			cout << endl;
		}
		cout << endl;
	}*/

	//0: 북, 1: 동, 2: 남, 3: 서
	//북
	for (int i = 1; i < N; i++)
		tilt_v(0, i, m);
	arrange(0, m);
	memset(visited, false, sizeof(visited));
	dfs(cnt + 1, m);
	memcpy(m, tmp, sizeof(tmp));


	//동
	for (int i = N - 2; i >= 0; i--)
		tilt_h(1, i, m);
	arrange(1, m);
	memset(visited, false, sizeof(visited));
	dfs(cnt + 1,m);

	memcpy(m, tmp, sizeof(tmp));

	//남
	for (int i = N - 2; i >= 0; i--)
		tilt_v(2, i,m);
	arrange(2,m);
	memset(visited, false, sizeof(visited));
	dfs(cnt + 1,m);

	memcpy(m, tmp, sizeof(tmp));

	//서
	for (int i = 1; i < N; i++)
		tilt_h(3, i, m);
	arrange(3, m);
	memset(visited, false, sizeof(visited));
	dfs(cnt + 1,m);

	memcpy(m, tmp, sizeof(tmp));
}

int main() {
	int map[MAX][MAX];

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	dfs(0, map);
	cout << rst << endl;
	return 0;
}

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

문제

문제

출처

ICPC

반례를 알아도 어디가 틀렸는지 모르겠습니다!

akscjsdl 5년 전 1

akscjsdl 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말