어항정리_23291.md

🐠 [23291] 어항정리

난이도: 플래티넘 5
소요 시간: 307분
메모리: 11868KB
시간: 84ms

리뷰

• 문제에서 원하는 로직이 많아서 순서대로 차근차근 풀어가야한다.
• 어항을 90도 회전하거나, 180도 회전할때 배열에 잘 저장시켜야한다. - 꼼꼼하게 한 단계씩 확인하면서 문제 풀기!

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_23291_어항정리 {
    static int N, K;
    static int min, max;
    static int[] fishbowl;
    static final int[] di = {0, 1};
    static final int[] dj = {1, 0};

    public static void main(String args[]) throws Exception {
        init();

        int round = 0;
        int[][] tmp_fishbowl = new int[N][N];
        int[][] tmp_moves = new int[N][N];

        while (max - min > K) {
            round++;
            insertFish();
            int[] HI = stackFishbowl1(tmp_fishbowl);
            moveFish(N - 1 - HI[0], HI[1], tmp_fishbowl, tmp_moves);
            flatFishbowl(tmp_fishbowl, tmp_moves);
            HI = stackFishbowl2(tmp_fishbowl);
            moveFish(N - HI[0], HI[1], tmp_fishbowl, tmp_moves);
            flatFishbowl(tmp_fishbowl, tmp_moves);
            checkMinMax();
        }
        System.out.println(round);
    }

    static void init() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        fishbowl = new int[N];
        max = 0;
        min = 10001;
        st = new StringTokenizer(br.readLine(), " ");

        for (int f = 0; f < N; f++) {
            fishbowl[f] = Integer.parseInt(st.nextToken());
            if (fishbowl[f] < min) min = fishbowl[f];
            else if (max < fishbowl[f]) max = fishbowl[f];
        }
    }

    static void insertFish() {
        for (int f = 0; f < N; f++) {
            if (fishbowl[f] == min) fishbowl[f]++;
        }
    }

    static int[] stackFishbowl1(int[][] tmp_fishbowl) {
        tmp_fishbowl[N - 1] = fishbowl.clone();

        int height = 1, width = 1;
        int remain = N - 1;
        int idx = 0;

        while (remain >= height) {
            int tmp_h = N - 1;
            for (int w = width - 1; w >= 0; w--) {
                tmp_h--;
                for (int h = 1; h <= height; h++) {
                    tmp_fishbowl[tmp_h][idx + width - 1 + h] = tmp_fishbowl[N - h][idx + w];
                    tmp_fishbowl[N - h][idx + w] = 0;
                }
            }
            idx += width;
            width = height;
            height = N - tmp_h;
            remain -= width;
        }

        return new int[]{height, idx};
    }

    static void moveFish(int i_len, int j_len, int[][] tmp_fishbowl, int[][] tmp_moves) {
        for (int j = j_len; j < N; j++) {
            for (int i = i_len; i < N; i++) {
                if (tmp_fishbowl[i][j] > 0) {
                    for (int z = 0; z < 2; z++) {
                        int ni = i + di[z];
                        int nj = j + dj[z];
                        if (ni < N && nj < N && tmp_fishbowl[ni][nj] > 0 && tmp_fishbowl[i][j] != tmp_fishbowl[ni][nj]) {
                            if (tmp_fishbowl[ni][nj] > tmp_fishbowl[i][j]) {
                                int fish = (tmp_fishbowl[ni][nj] - tmp_fishbowl[i][j]) / 5;
                                tmp_moves[ni][nj] -= fish;
                                tmp_moves[i][j] += fish;
                            } else {
                                int fish = (tmp_fishbowl[i][j] - tmp_fishbowl[ni][nj]) / 5;
                                tmp_moves[i][j] -= fish;
                                tmp_moves[ni][nj] += fish;
                            }
                        }
                    }
                }
            }
        }
    }

    static void flatFishbowl(int[][] tmp_fishbowl, int[][] tmp_moves) {
        int idx_fishbowl = 0;
        for (int j = 0; j < N; j++) {
            for (int i = N - 1; i >= 0; i--) {
                if (tmp_fishbowl[i][j] > 0) {
                    fishbowl[idx_fishbowl++] = tmp_fishbowl[i][j] + tmp_moves[i][j];
                    tmp_moves[i][j] = 0;
                    tmp_fishbowl[i][j] = 0;
                }
            }
        }
    }

    static int[] stackFishbowl2(int[][] tmp_fishbowl) {
        tmp_fishbowl[N - 1] = fishbowl.clone();

        int height = 1;
        int width = N;
        int idx = 0;

        for (int r = 0; r < 2; r++) {
            for (int h = 0; h < height; h++) {
                for (int w = 0; w < width / 2; w++) {
                    tmp_fishbowl[N - 1 - height - h][idx + width / 2 + w] =
                            tmp_fishbowl[N - height + h][idx + width / 2 - 1 - w];
                    tmp_fishbowl[N - height + h][idx + width / 2 - 1 - w] = 0;
                }
            }
            width = width / 2;
            height = height * 2;
            idx += width;
        }
        return new int[]{height, idx};
    }

    static void checkMinMax() {
        max = 0;
        min = 10001;
        for (int f = 0; f < N; f++) {
            if (fishbowl[f] > 0 && fishbowl[f] < min) min = fishbowl[f];
            if (max < fishbowl[f]) max = fishbowl[f];
        }
    }
}