백준 23291번 : 어항 정리 - 시뮬레이션 C++

https://www.acmicpc.net/problem/23291

23291번: 어항 정리

#include <bits/stdc++.h>

using namespace std;

int N, K, arr[101][101];

void addFish() {
    int min = INT_MAX;
    for (int i = 1; i <= N; i++) {
        if (arr[1][i] < min) min = arr[1][i];
    }

    for (int i = 1; i <= N; i++) {
        if (arr[1][i] == min) arr[1][i]++;
    }
}

void jumpBlock() {
    arr[2][2] = arr[1][1];
    arr[1][1] = 0;

    int stx = 2, sty = 2;
    int row = 2, col = 1;
    int cnt = 1;

    while (stx + sty <= N) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                arr[2 + j][sty + (row - i)] = arr[stx - i][sty - j];
                arr[stx - i][sty - j] = 0;
            }
        }

        sty += stx;
        if (cnt % 2 == 1) {
            col++;
        } else {
            row++;
            stx++;
        }

        cnt++;
    }
}


void fishControl() {
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    int tmp[101][101];
    memset(tmp, 0, sizeof(tmp));

    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j]) {
                int sum = 0;
                int minus = 0;

                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx <= 0 || nx > 100 || ny <= 0 || ny > N) continue;
                    if (arr[nx][ny] == 0)continue;

                    int diff = (arr[i][j] - arr[nx][ny]) / 5;

                    if (diff == 0) continue;
                    else if (diff > 0) {
                        minus += diff;
                    } else {
                        sum += abs(diff);
                    }
                }
                tmp[i][j] = arr[i][j] - minus + sum;
            }
        }
    }
    swap(tmp, arr);
}

void putDown() {
    int idx = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 100; j++) {
            if (arr[j][i]) {
                arr[1][idx++] = arr[j][i];

                if (j == 1 && i == idx - 1) continue;
                arr[j][i] = 0;
            }
        }
    }
}


void reJumpBlock() {
    for (int i = 1; i <= N / 2; i++) {
        arr[2][N - i + 1] = arr[1][i];
        arr[1][i] = 0;
    }

    for (int i = 0; i < N / 4; i++) {
        for (int j = 0; j < 2; j++) {
            arr[3 + j][N - i] = arr[2 - j][N / 2 + 1 + i];
            arr[2 - j][N / 2 + 1 + i] = 0;
        }
    }
}

bool isEnd() {
    int max = -1;
    int min = INT_MAX;

    for (int i = 1; i <= N; i++) {
        if (max < arr[1][i]) max = arr[1][i];
        if (min > arr[1][i]) min = arr[1][i];
    }
    return (max - min <= K);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> arr[1][i];
    }

    if (isEnd()) {
        cout << 0 << '\n';
        return 0;
    }

    int ans = 1;
    while (1) {
        addFish();
        jumpBlock();
        fishControl();
        putDown();
        reJumpBlock();
        fishControl();
        putDown();
        if (isEnd()) break;
        ans++;
    }


    cout << ans << '\n';

    return 0;
}