백준 12100 2048 (Easy) (c++) : 피너클

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

귀찮은 구현 문제다.

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	cout << solve(0) << endl;
}

입력받고 solve()함수를 돌릴것이다.

solve함수를 보기전에 함수 2개를 먼저 보자.

void init(int b[21][21]) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			map[i][j] = b[i][j];
}

map배열을 원래 배열로 돌려주는 함수다.

int m() {
	int ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			ans = max(ans, map[i][j]);
	return ans;
}

map배열에서 가장 큰 숫자를 리턴하는 함수다.

left, right, up, down함수는 단순 구현이어서 딱히 보여줄것이 없다. up 하나만 본다면

void up() {
	bool before = false;
	for (int i = 0; i < n; i++) {
		before = false;

before는 이전에 합쳐진적이 있는지를 확인한다. 

2	2	2
2	2	2
4	4	4

위의 배열을 위로 옮길때 맨 처음 2개가 먼저 합쳐진다.

4	4	4
4	4	4

그후 맨 아래 숫자가 위로 올라가야 하는데 여기서 숫자가 서로 합쳐지면 안된다.

8	8	8

위와 같이 되면 안되는 것이다. 그렇기에 before로 이전에 합쳐졌다면 이번 숫자는 합치지 않고 올리는 것이다.

		for (int j = 1; j < n; j++) {
			if (map[j][i] == 0) continue;

만약 현재 숫자가 0이라면 뒤를 무시한다.

			for (int k = j - 1; k >= 0; k--) {
				if (map[k][i] == 0) {
					map[k][i] = map[k + 1][i];
					map[k + 1][i] = 0;
				}
				else if (map[k][i] == map[k + 1][i] && !before) {
					before = true;
					map[k][i] *= 2;
					map[k + 1][i] = 0;
					break;
				}
				else {
					before = false;
					break;
				}
			}

만약 위에가 0이라면 비어있다는 뜻이니 현재 칸을 위로 올린다.

만약 현재 칸과 위의 칸의 숫자가 같고 before가 false라면 서로를 합친다.

이도 아니라면 위에 칸에 현재 칸과는 전혀 다른 숫자가 있다는 뜻이다. before를 false로 바꾸고 반복에서 나온다.

 

위의 함수를 left, right, down용으로 또 따로 만들면 된다. 이는 생략하겠다.

int solve(int num) {
	if (num == 5) return 0;
	int first[21][21];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			first[i][j] = map[i][j];
	int ans = 0;
	up();
	ans = max(ans, m());
	ans = max(ans, solve(num + 1));
	init(first);
	down();
	ans = max(ans, m());
	ans = max(ans, solve(num + 1));
	init(first);
	left();
	ans = max(ans, m());
	ans = max(ans, solve(num + 1));
	init(first);
	right();
	ans = max(ans, m());
	ans = max(ans, solve(num + 1));
	init(first);
	return ans;
}

solve함수다. 길어서 복잡해 보이지만 단순하다.

만약 num이 5라면 이미 5번 돌린것이니 0을 리턴한다.

그후 first배열에 현재 map배열을 저장한다. 칸들을 옮긴뒤 초기화 할때 사용할 것이다.

ans에는 현재에서 가장 큰 숫자가 저장된다.

이제 위로 올리고 ans에 가장 큰 숫자를 저장한뒤 위로 옮긴 상태에서 solve를 돌리고 초기화를 하면 된다.

이를 왼쪽, 오른쪽, 아래도 똑같이 하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
int map[21][21];

void up() {
	bool before = false;
	for (int i = 0; i < n; i++) {
		before = false;
		for (int j = 1; j < n; j++) {
			if (map[j][i] == 0) continue;
			for (int k = j - 1; k >= 0; k--) {
				if (map[k][i] == 0) {
					map[k][i] = map[k + 1][i];
					map[k + 1][i] = 0;
				}
				else if (map[k][i] == map[k + 1][i] && !before) {
					before = true;
					map[k][i] *= 2;
					map[k + 1][i] = 0;
					break;
				}
				else {
					before = false;
					break;
				}
			}
		}
	}
}
void down() {
	bool before = false;
	for (int i = 0; i < n; i++) {
		before = false;
		for (int j = n-2; j >= 0; j--) {
			if (map[j][i] == 0) continue;
			for (int k = j; k < n; k++) {
				if (map[k + 1][i] == 0) {
					map[k + 1][i] = map[k][i];
					map[k][i] = 0;
				}
				else if (map[k][i] == map[k + 1][i] && !before) {
					before = true;
					map[k + 1][i] *= 2;
					map[k][i] = 0;
					break;
				}
				else {
					before = false;
					break;
				}
			}
		}
	}
}
void right() {
	bool before = false;
	for (int i = 0; i < n; i++) {
		before = false;
		for (int j = n - 2; j >= 0; j--) {
			if (map[i][j] == 0) continue;
			for (int k = j; k < n; k++) {
				if (map[i][k+1] == 0) {
					map[i][k+1] = map[i][k];
					map[i][k] = 0;\
				}
				else if (map[i][k] == map[i][k+1] && !before) {
					before = true;
					map[i][k+1] *= 2;
					map[i][k] = 0;
					break;
				}
				else {
					before = false;
					break;
				}
			}
		}
	}
}
void left() {
	bool before = false;
	for (int i = 0; i < n; i++) {
		before = false;
		for (int j = 1; j < n; j++) {
			if (map[i][j] == 0) continue;
			for (int k = j - 1; k >= 0; k--) {
				if (map[i][k] == 0) {
					map[i][k] = map[i][k+1];
					map[i][k+1] = 0;\
				}
				else if (map[i][k] == map[i][k+1] && !before) {
					before = true;
					map[i][k] *= 2;
					map[i][k+1] = 0;
					break;
				}
				else {
					before = false;
					break;
				}
			}
		}
	}
}
void init(int b[21][21]) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			map[i][j] = b[i][j];
}
int m() {
	int ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			ans = max(ans, map[i][j]);
	return ans;
}
int solve(int num) {
	if (num == 5) return 0;
	int first[21][21];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			first[i][j] = map[i][j];
	int ans = 0;
	up();
	ans = max(ans, m());
	ans = max(ans, solve(num + 1));
	init(first);
	down();
	ans = max(ans, m());
	ans = max(ans, solve(num + 1));
	init(first);
	left();
	ans = max(ans, m());
	ans = max(ans, solve(num + 1));
	init(first);
	right();
	ans = max(ans, m());
	ans = max(ans, solve(num + 1));
	init(first);
	return ans;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	cout << solve(0) << endl;
}

전체코드다.