[PS] 백준 23291번: 어항 정리

어항 정리

하라는 대로만 하니깐 그냥 풀렸는데 하라는게 너무 많다.... ㅡ,ㅡ

큐빙에 이어서 솔브닥에 등록된 내 두번째 플레 문제이다. 다른 유형이었으면 플레 손도 못댔을텐데, 역시 날 도와주는건 구현 유형밖에 없다.

 

#include <bits/stdc++.h>

#define FOR(i, n) for(int i = 0; i < int(n); i++)
#define FORL(e, s) for(auto &e : s)
#define endl "\n"
#define vi vector<int>

using namespace std;

int N, K;
int MAP[100][100];

int dr[4] = { -1, +0, +1, +0 };
int dc[4] = { +0, +1, +0, -1 };
#define iib(r, c) (0 <= r && r < N && 0 <= c && c < N)

void put_fishes() {
    int cMAP[100][100];
    copy(&MAP[0][0], &MAP[0][0] + 100 * 100, &cMAP[0][0]);

    FOR(r, N) {
        FOR(c, N) {
            int orval = cMAP[r][c];
            FOR(i, 4) {
                int nr = r + dr[i], nc = c + dc[i];
                if (!iib(nr, nc)) continue;
                if (cMAP[nr][nc] == 0) continue;
                int tarval = cMAP[nr][nc];
                if (orval > tarval) {
                    int d = (orval - tarval) / 5;
                    if (d > 0) {
                        MAP[r][c] -= d;
                        MAP[nr][nc] += d;
                    }
                }
            }
        }
    }
}

void put_in_floor() {
    vi v;
    for (int j = 0; j < N; j++) {
        for (int i = N - 1; i >= 0; i--) {
            if (MAP[i][j] == 0) break;
            v.push_back(MAP[i][j]);
        }
    }

    memset(MAP, 0, sizeof(int) * 100 * 100);

    FOR(j, N) {
        MAP[N - 1][j] = v[j];
    }
}

void simulate() {
    int minval = 987654321;
    FOR(j, N) minval = min(minval, MAP[N - 1][j]);
    FOR(j, N) if(MAP[N - 1][j] == minval) MAP[N - 1][j] += 1;

    MAP[N - 2][0] = MAP[N - 1][0];
    FOR(j, N - 1) MAP[N - 1][j] = MAP[N - 1][j + 1];
    MAP[N - 1][N - 1] = 0;

    bool doit = true;
    while (doit) {
        int cMAP[100][100];
        copy(&MAP[0][0], &MAP[0][0] + 100 * 100, &cMAP[0][0]);

        int tidx = 0;
        while(true) {
            if (cMAP[N - 2][tidx] == 0) break;
            tidx += 1;
        }
        vector<vi> vv;
        FOR(i, tidx) {
            vi v;
            for (int i = N - 1; i >= 0; i--) {
                if (cMAP[i][0] == 0) { break; }
                else { v.push_back(cMAP[i][0]); }
            }
            vv.push_back(v);
            FOR(i, N) FOR(j, N - 1) cMAP[i][j] = cMAP[i][j + 1];
            FOR(i, N) cMAP[i][N - 1] = 0;
        }
        int trow = N - 2;
        while(!vv.empty()) {
            auto v = vv.back(); vv.pop_back();
            FOR(j, v.size()) cMAP[trow][j] = v[j];
            trow -= 1;
        }
 
        int down2nd = 0, down1st = 0;
        FOR(j, N) if(cMAP[N - 1][j] != 0) { down1st += 1; }
        FOR(j, N) if(cMAP[N - 2][j] != 0) { down2nd += 1; }

        if (down1st < down2nd) { doit = false; break; } 
        else { copy(&cMAP[0][0], &cMAP[0][0] + 100 * 100, &MAP[0][0]); }  
    }

    put_fishes();
    put_in_floor();

    vi v;
    FOR(j, N / 2) { v.push_back(MAP[N - 1][j]); }
    FOR(j, N / 2) {
        MAP[N - 1][j] = MAP[N - 1][j + N / 2];
        MAP[N - 1][j + N / 2] = 0;
    }
    FOR(j, N / 2) { MAP[N - 2][j] = v.back(); v.pop_back(); }

    vector<vi> vv;
    v.clear();
    for (int i = N - 1; i >= N - 2; i--) {
        FOR(j, N / 4) { v.push_back(MAP[i][j]); }
        vv.push_back(v);
    }

    for(int i = N - 3; i >= N - 4; i--) {
        auto vec = vv.back(); vv.pop_back();
        FOR(j, N / 4) {
            MAP[i][j] = vec.back(); vec.pop_back();
        }
    }

    for (int i = N - 1; i >= N - 2; i--) {
        FOR(j, N / 4) {
            MAP[i][j] = MAP[i][j + N / 4];
            MAP[i][j + N / 4] = 0;
        }
    }

    put_fishes();
    put_in_floor();
}

int main() {
    cin >> N >> K;
    FOR(j, N) cin >> MAP[N - 1][j];

    for(int cnt = 0;;cnt++) {
        int MIN = 987654321, MAX = -987654321;
        FOR(j, N) {
            MIN = min(MIN, MAP[N - 1][j]);
            MAX = max(MAX, MAP[N - 1][j]);
        }
        if (MAX - MIN <= K) {
            cout << cnt << endl;
            return 0;
        }
        simulate();
    }
}