PS/Problems
[Java] 백준 12094번 2048 (Hard) - 빡구현
CalicoCat22
2022. 2. 18. 16:38
https://www.acmicpc.net/problem/12094
12094번: 2048 (Hard)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
12100번 2048(Easy)와 유사하지만
수행이 5번인 easy와 다르게 10번이나 되어서 빡센 가지치기가 필요했다.
3시간 걸림;
import java.util.*;
import java.io.*;
public class p4_12094 {
static FastScanner fs = new FastScanner();
static PrintWriter pw = new PrintWriter(System.out);
static int n, ans = 0;
static int[][][] table;
static int[][] temp;
public static void main(String[] args) {
n = fs.nextInt();
table = new int[11][n][n];
int max = 0;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
table[0][i][j] = fs.nextInt();
max = Math.max(max, table[0][i][j]);
}
}
for (int i=0;i<4;i++){
solve(0, i, max);
}
// for (int i=0;i<n;i++){
// for (int j=0;j<n;j++){
// pw.print(table[10][i][j] + " ");
// }
// pw.println();
// }
pw.println(ans);
pw.close();
}
static void solve(int ver, int k, int max){
if (max * Math.pow(2, 10 - ver) <= ans) return;
for (int[] a : table[ver + 1]){
Arrays.fill(a, 0);
}
if (k == 0){
for (int i=0;i<n;i++){
int p1 = 0, p2 = 0, p3 = 0;
while (true){
while (p2 < n && table[ver][i][p2] == 0) p2++;
if (p2 >= n) break;
p3 = p2 + 1;
while (p3 < n && table[ver][i][p3] == 0) p3++;
if (p3 >= n){
table[ver + 1][i][p1] = table[ver][i][p2];
break;
}
if (table[ver][i][p2] == table[ver][i][p3]){
table[ver + 1][i][p1++] = table[ver][i][p2] * 2;
if (table[ver][i][p2] == max) max *= 2;
p2 = p3 + 1;
}
else{
table[ver + 1][i][p1++] = table[ver][i][p2];
p2 = p3;
}
}
}
}
else if (k == 1){
for (int i=0;i<n;i++){
int p1 = n - 1, p2 = n - 1, p3 = n - 1;
while (true){
while (p2 >= 0 && table[ver][i][p2] == 0) p2--;
if (p2 < 0) break;
p3 = p2 - 1;
while (p3 >= 0 && table[ver][i][p3] == 0) p3--;
if (p3 < 0){
table[ver + 1][i][p1] = table[ver][i][p2];
break;
}
if (table[ver][i][p2] == table[ver][i][p3]){
table[ver + 1][i][p1--] = table[ver][i][p2] * 2;
if (table[ver][i][p2] == max) max *= 2;
p2 = p3 - 1;
}
else{
table[ver + 1][i][p1--] = table[ver][i][p2];
p2 = p3;
}
}
}
}
else if (k == 2){
for (int i=0;i<n;i++){
int p1 = 0, p2 = 0, p3 = 0;
while (true){
while (p2 < n && table[ver][p2][i] == 0) p2++;
if (p2 >= n) break;
p3 = p2 + 1;
while (p3 < n && table[ver][p3][i] == 0) p3++;
if (p3 >= n){
table[ver + 1][p1][i] = table[ver][p2][i];
break;
}
if (table[ver][p2][i] == table[ver][p3][i]){
table[ver + 1][p1++][i] = table[ver][p2][i] * 2;
if (table[ver][p2][i] == max) max *= 2;
p2 = p3 + 1;
}
else{
table[ver + 1][p1++][i] = table[ver][p2][i];
p2 = p3;
}
}
}
}
else{
for (int i=0;i<n;i++){
int p1 = n - 1, p2 = n - 1, p3 = n - 1;
while (true){
while (p2 >= 0 && table[ver][p2][i] == 0) p2--;
if (p2 < 0) break;
p3 = p2 - 1;
while (p3 >= 0 && table[ver][p3][i] == 0) p3--;
if (p3 < 0){
table[ver + 1][p1][i] = table[ver][p2][i];
break;
}
if (table[ver][p2][i] == table[ver][p3][i]){
table[ver + 1][p1--][i] = table[ver][p2][i] * 2;
if (table[ver][p2][i] == max) max *= 2;
p2 = p3 - 1;
}
else{
table[ver + 1][p1--][i] = table[ver][p2][i];
p2 = p3;
}
}
}
}
if (ver + 1 == 10){
ans = Math.max(ans, max);
}
else{
for (int i=0;i<4;i++){
solve(ver + 1, i, max);
}
}
}
// ----------input function----------
static void sort(int[] a) {
ArrayList<Integer> L = new ArrayList<>();
for (int i : a)
L.add(i);
Collections.sort(L);
for (int i = 0; i < a.length; i++)
a[i] = L.get(i);
}
static class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while (!st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
int[] readArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
long nextLong() {
return Long.parseLong(next());
}
}
}