글 읽기 - 12퍼에서 틀렸습니다. 전략이 잘못된건가요?

specimen 4년 전 0

안녕하세요.

코드 말고 제가 짠 알고리즘이라도 봐주시면 감사하겠습니다.

현재에서 다음을 검사한다. 다음값이 같은값이면 현재값에서 2배하고 다음값을 0으로!
연산을 해준 후에 (만약에 UP일때), UP이므로 위에서 부터 차례대로 값이 나와야 한다.
따라서 위에서 부터 순차적으로 0이 아닌 값을 큐에 넣고, 위에서 차례대로 큐에서 POP을 하여 값을 삽입(큐 사이즈가 0일 때 까지)!

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 21
int map[MAX][MAX];
int n;
int ret;

void input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
}

// 현재에서 다음을 검사한다. 다음값이 같은값이면 현재값에서 2배하고 다음값을 0으로!
// 연산을 해준 후에 (만약에 UP일때), UP이므로 위에서 부터 차례대로 값이 나와야 한다.
// 따라서 위에서 부터 순차적으로 0이 아닌 값을 큐에 넣고, 위에서 차례대로 큐에서 POP을 하여
// 값을 삽입 (큐 사이즈가 0일 때 까지)!
void move(int num) {
    switch (num) {
        case 0:// UP
            // CHECK
            for (int x = 0; x < n; x++) {
                for (int y = n - 1; y > 0; y--) {
                    if (map[y][x] == map[y - 1][x]) {
                        map[y][x] *= 2;
                        map[y - 1][x] = 0;
                    }
                }
            }

            // PUSH
            for (int x = 0; x < n; x++) {
                queue<int> q;
                for (int y = 0; y < n; y++) {
                    if (map[y][x] == 0) continue;
                    q.push(map[y][x]);
                    map[y][x] = 0;
                }
                int yy = 0;
                while (!q.empty()) {
                    int nn = q.front();
                    map[yy][x] = nn;
                    yy++;
                    q.pop();
                }
            }
            break;

        case 1: // DOWN
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n - 1; y++) {
                    if (map[y][x] == map[y + 1][x]) {
                        map[y][x] *= 2;
                        map[y + 1][x] = 0;
                    }
                }
            }
            // PUSH
            for (int x = 0; x < n; x++) {
                queue<int> q;
                for (int y = n - 1; y >= 0; y--) {
                    if (map[y][x] == 0) continue;
                    q.push(map[y][x]);
                    map[y][x] = 0;
                }
                int yy = n - 1;
                while (!q.empty()) {
                    int nn = q.front();
                    map[yy][x] = nn;
                    yy--;
                    q.pop();
                }
            }
            break;
        case 2: // RIGHT
            for (int y = 0; y < n; y++) {
                for (int x = 0; x < n - 1; x++) {
                    if (map[y][x] == map[y][x + 1]) {
                        map[y][x] *= 2;
                        map[y][x + 1] = 0;
                    }
                }
            }
            // PUSH
            for (int y = 0; y < n; y++) {
                queue<int> q;
                for (int x = n - 1; x >= 0; x--) {
                    if (map[y][x] == 0) continue;
                    q.push(map[y][x]);
                    map[y][x] = 0;
                }
                int xx = n - 1;
                while (!q.empty()) {
                    int nn = q.front();
                    map[y][xx] = nn;
                    xx--;
                    q.pop();
                }
            }
            break;
        case 3: // LEFT
            for (int y = 0; y < n; y++) {
                for (int x = n - 1; x > 0; x--) {
                    if (map[y][x] == map[y][x - 1]) {
                        map[y][x] *= 2;
                        map[y][x - 1] = 0;
                    }
                }
            }
            // PUSH
            for (int y = 0; y < n; y++) {
                queue<int> q;
                for (int x = 0; x < n; x++) {
                    if (map[y][x] == 0) continue;
                    q.push(map[y][x]);
                    map[y][x] = 0;
                }
                int xx = 0;
                while (!q.empty()) {
                    int nn = q.front();
                    map[y][xx] = nn;
                    xx++;
                    q.pop();
                }
            }
            break;
    }
}



// 위, 아래, 오른쪽, 왼쪽으로 밀기
void dfs(int cnt) {
    if (cnt == 5) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ret = max(ret, map[i][j]);
            }
        }
        return;
    }
    int temp[MAX][MAX];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            temp[i][j] = map[i][j];
        }
    }
    for (int a = 0; a < 4; a++) {
        move(a);
        dfs(cnt + 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = temp[i][j];
            }
        }
    }
}


int main() {
    input();
    dfs(0);
    cout << ret << "\n";
}

eodlsgh123 3년 전 0

안녕하세요 저도 12 % 에서 틀렸다고 나오는데

지금은 해결 하셧나요 ? 혹시 해결하셧으면 12 % 반례를 알 수 있을가요 ? ㅠ

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

문제

문제

출처

ICPC

12퍼에서 틀렸습니다. 전략이 잘못된건가요?

specimen 4년 전 0

eodlsgh123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말