백준 Gold 1 2048 (Easy)
2048 (Easy) (백준 Gold 1)
https://www.acmicpc.net/problem/12100
2048 게임을 5번 플레이하며
가장 높은 숫자의 값을 구하는 문제
풀이 방법
일단 브루트 포스 + 백트래킹 계열이다
문제의 요점은
- 이동
- 블럭합치기
- 다시 이동
의 순서가 중점인데
-
‘이동’을 통하여
먼저 블럭들을 ‘가까이’ 둔다 -
이후 ‘합칠 블럭’들을 합쳐주고
-
빈 공간을 다시 ‘밀어 넣어’주는 것이 요점
그 외에는
- 2048 이지만 사실은 그 이상의 값이 발생할 수 있기에 n을 long으로 잡은 것
- n이 1일때의 예외처리
등이 있다
n이 20 이하이기에 n^3 이상의 알고리즘을 사용해도 문제가 없었고
그렇기에 동시에 브루트포스 라는 것을 직감하였다
문제를 ‘조금 더’ 정확하게 분석하였다면
더 로직을 쉽게 잡았을 것이라 생각한다
제출 코드
#include<iostream>
#include<vector>
using namespace std;
const int lim = 5;
int n;
int move(vector<vector<long>>& maps, int dir)
{
int bestV = 0;
switch (dir)
{
case 0: // up
{
// 이동 페이즈
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n; j++)
{
int temp = i;
while (temp < n &&
maps[temp][j] == 0)
{
temp++;
}
if (temp == i)
continue;
if (temp == n)
continue;
maps[i][j] = maps[temp][j];
maps[temp][j] = 0;
}
}
// 한번 합치는 페이즈
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n; j++)
{
if (maps[i][j] == maps[i + 1][j])
{
maps[i][j] *= 2;
maps[i + 1][j] = 0;
}
if (maps[i][j] > bestV)
bestV = maps[i][j];
}
}
// 이동 페이즈
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n; j++)
{
int temp = i;
while (temp < n &&
maps[temp][j] == 0)
{
temp++;
}
if (temp == i)
continue;
if (temp == n)
continue;
maps[i][j] = maps[temp][j];
maps[temp][j] = 0;
}
}
}
break;
case 1: // down
{
// 이동 페이즈
for (int i = n - 1; i > 0; i--)
{
for (int j = 0; j < n; j++)
{
int temp = i;
while (temp >= 0 &&
maps[temp][j] == 0)
{
temp--;
}
if (temp == i)
continue;
if (temp < 0)
continue;
maps[i][j] = maps[temp][j];
maps[temp][j] = 0;
}
}
// 한번 합치는 페이즈
for (int i = n - 1; i > 0; i--)
{
for (int j = 0; j < n; j++)
{
if (maps[i][j] == maps[i - 1][j])
{
maps[i][j] *= 2;
maps[i - 1][j] = 0;
}
if (maps[i][j] > bestV)
bestV = maps[i][j];
}
}
// 이동 페이즈
for (int i = n - 1; i > 0; i--)
{
for (int j = 0; j < n; j++)
{
int temp = i;
while (temp >= 0 &&
maps[temp][j] == 0)
{
temp--;
}
if (temp == i)
continue;
if (temp < 0)
continue;
maps[i][j] = maps[temp][j];
maps[temp][j] = 0;
}
}
}
break;
case 2: // right
{
for (int j = n - 1; j > 0; j--)
{
for (int i = 0; i < n; i++)
{
int temp = j;
while (temp >= 0
&& maps[i][temp] == 0)
{
temp--;
}
if (temp == j)
continue;
if (temp < 0)
continue;
maps[i][j] = maps[i][temp];
maps[i][temp] = 0;
}
}
for (int j = n - 1; j > 0; j--)
{
for (int i = 0; i < n; i++)
{
if (maps[i][j] == maps[i ][j - 1])
{
maps[i][j] *= 2;
maps[i][j - 1] = 0;
}
if (maps[i][j] > bestV)
bestV = maps[i][j];
}
}
for (int j = n - 1; j > 0; j--)
{
for (int i = 0; i < n; i++)
{
int temp = j;
while (temp >= 0
&& maps[i][temp] == 0)
{
temp--;
}
if (temp == j)
continue;
if (temp < 0)
continue;
maps[i][j] = maps[i][temp];
maps[i][temp] = 0;
}
}
}
break;
case 3: // left
{
for (int j = 0; j < n - 1; j++)
{
for (int i = 0; i < n; i++)
{
int temp = j;
while (temp < n &&
maps[i][temp] == 0)
{
temp++;
}
if (temp == j)
continue;
if (temp == n)
continue;
maps[i][j] = maps[i][temp];
maps[i][temp] = 0;
}
}
for (int j = 0; j < n-1; j++)
{
for (int i = 0; i < n; i++)
{
if (maps[i][j] == maps[i][j + 1])
{
maps[i][j] *= 2;
maps[i][j + 1] = 0;
}
if (maps[i][j] > bestV)
bestV = maps[i][j];
}
}
for (int j = 0; j < n - 1; j++)
{
for (int i = 0; i < n; i++)
{
int temp = j;
while (temp < n &&
maps[i][temp] == 0)
{
temp++;
}
if (temp == j)
continue;
if (temp == n)
continue;
maps[i][j] = maps[i][temp];
maps[i][temp] = 0;
}
}
}
break;
}
return bestV;
}
int recur(vector<vector<long>>& maps, int best, int count)
{
if (count == lim)
{
return best;
}
for (int i = 0; i < 4; i++)
{
vector<vector<long>> origin = maps;
best = max(best, move(maps, i));
best = max(best, recur(maps, best, count + 1));
maps = origin;
}
return best;
}
int main()
{
cin >> n;
vector<vector<long>> maps(n, vector<long>(n, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> maps[i][j];
if (n == 1)
cout << maps[0][0];
else
cout << recur(maps, 0, 0);
return 0;
}
결과
수많은 오답이 있었던 만큼
고생을 좀 하였다
구현 문제는 단순해보이지만
‘구현’에 실패하였을때, 스스로 반례를 찾고
원인을 파악한 후, 재수정하는 것의 반복이기에
실제로는 매우 어려운 계열의 문제이다
내가 제출한 코드만 보더라도
‘이동’, ‘재귀’, ‘n’에 대한 예외처리 등에 대한 부분을
전부 조금씩 고려하지 못하여 틀린 부분이 많았었다
이걸 웹 등에서 풀어야 한다면 상당한 고역일 것으로 보인다
댓글남기기