[C++] 2048 (Easy) - 브루트포스, 구현, 시뮬레이션

#include <iostream>
#include <vector>
#include <string.h>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 22

using namespace std;
typedef long long int lld;

int N;  //보드의 크기
lld map[MAX_N][MAX_N];  //보드
lld mv;  //max_value

void input()
{
    cin >> N;
    LOOP(i, N) {
        LOOP(j, N) {
            cin >> map[i][j];
            if(map[i][j]>mv) mv=map[i][j];
        }
    }
}

void f(int cnt, lld map[MAX_N][MAX_N])
{
    if(cnt==5) return;
    
    lld fmap[5][MAX_N][MAX_N];
    
    memset(fmap, 0, sizeof(lld)*5*MAX_N*MAX_N);
    
    for(int i=1; i<=N; i++) {  //위로
        vector<lld> v;
        
        lld x=0;
        for(int j=1; j<=N; j++) {
            lld y=map[j][i];
            if(y) {
                if(x) {
                    if(x == y) {
                        if(x*2>mv) mv=x*2;
                        v.push_back(x*2); x=0;
                    }
                    else {
                        v.push_back(x); x=y;
                    }
                }
                else x=y;
            }
        }
        if(x) v.push_back(x);
        LOOP(j, v.size()) fmap[1][j][i]=v[j-1];
    } f(cnt+1, fmap[1]);
    for(int i=1; i<=N; i++) {  //위로
        vector<lld> v;
        
        lld x=0;
        for(int j=1; j<=N; j++) {
            lld y=map[i][j];
            if(y) {
                if(x) {
                    if(x == y) {
                        if(x*2>mv) mv=x*2;
                        v.push_back(x*2); x=0;
                    }
                    else {
                        v.push_back(x); x=y;
                    }
                }
                else x=y;
            }
        }
        if(x) v.push_back(x);
        LOOP(j, v.size()) fmap[2][i][j]=v[j-1];
    } f(cnt+1, fmap[2]);
    for(int i=1; i<=N; i++) {  //위로
        vector<lld> v;
        
        lld x=0;
        for(int j=N; j>=1; j--) {
            lld y=map[j][i];
            if(y) {
                if(x) {
                    if(x == y) {
                        if(x*2>mv) mv=x*2;
                        v.push_back(x*2); x=0;
                    }
                    else {
                        v.push_back(x); x=y;
                    }
                }
                else x=y;
            }
        }
        if(x) v.push_back(x);
        LOOP(j, v.size()) fmap[3][N+1-j][i]=v[j-1];
    } f(cnt+1, fmap[3]);
    for(int i=1; i<=N; i++) {  //위로
        vector<lld> v;
        
        lld x=0;
        for(int j=N; j>=1; j--) {
            lld y=map[i][j];
            if(y) {
                if(x) {
                    if(x == y) {
                        if(x*2>mv) mv=x*2;
                        v.push_back(x*2); x=0;
                    }
                    else {
                        v.push_back(x); x=y;
                    }
                }
                else x=y;
            }
        }
        if(x) v.push_back(x);
        LOOP(j, v.size()) fmap[4][i][N+1-j]=v[j-1];
    } f(cnt+1, fmap[4]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    f(0, map);
    
    cout << mv;
    
    return 0;
}

솔직히 힘들었다. 알고리즘이 어렵다기 보다는 코드가 너무 길어서 수정하는데에 많이 헷갈렸던 것 같다. 솔직히 이렇게나 긴 코드를 짜는 것은 문제 풀면서 거의 처음인 것 같다.

 

내가 짠 코드의 알고리즘을 적어보려고 했는데 다른 사람의 코드를 보니까 더 낫기도 하고 4ms가 걸려서 다른 사람의 코드랑 그 알고리즘을 적어봤다.

 

4ms가 걸린 이유는 거의 똑같지만 나는 stack을 쓰고 memset으로 초기화를 했으며 배열을 여러 개를 사용했기 때문이다.

 

 

<참조한 코드>

https://www.acmicpc.net/source/12640660

로그인

<알고리즘>

1. 위로 올린다.
2. 최댓값을 판단한다.  ->  이 배열로 다시 함수를 돌린다.
3. 반시계 방향으로 돌린다.
4. 1~3을 4번 반복한다.

 

<반례 모음>

https://www.acmicpc.net/board/view/61812

글 읽기 - <<12100번 반례모음>>

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.