백준 2630. 색종이 만들기

문제 링크

난이도	정답률(_%)
Silver 3	72.172%

설계

• 종이의 길이 N <= 128
• 문제 설명대로 종이의 색이 전부 같지 않으면 분할

시간 복잡도

• 종이 색이 모두 같은지 비교 N^2
  • 같지 않으면 크기를 1/4로 나눠서 반복 (1/4*N)^2 * 4
• O(N^2)

공간 복잡도

• 색종이 공간을 저장하는 int형 이차원 배열
• 색종이 색 조각 개수를 저장하는 int형 배열, 길이 2

풀이

• 종이의 색이 모두 같은지 확인한다
  • 색이 같으면 해당 색의 Count를 늘린다.
  • 색이 같지 않으면, 종이를 4등분하여 종이의 색이 같을 때 까지 반복한다.

결과

메모리	실행 시간
16668KB	128ms

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int length = Integer.parseInt(br.readLine());
        Paper colorPaper = new Paper(length);

        for (int i = 0; i < length; i++) {
            colorPaper.setPaperColor(i, br.readLine().split(" "));
        }

        colorPaper.devidePaper(new Location(0, 0), new Location(length - 1, length - 1));

        bw.write(Integer.toString(colorPaper.getWhitePaperCount()));
        bw.write("\n");
        bw.write(Integer.toString(colorPaper.getBluePaperCount()));
        bw.flush();
        bw.close();
    }
}

class Paper {
    private int[][] paper;
    private int length;
    private int[] paperCount;

    public Paper(int length) {
        this.length = length;
        this.paper = new int[length][length];
        this.paperCount = new int[2];
    }

    public void setPaperColor(int row, String[] paperRow) {
        for (int i = 0; i < length; i++) {
            paper[row][i] = Integer.parseInt(paperRow[i]);
        }
    }

    public void devidePaper(Location start, Location end) {
        if (checkAllColorSame(start, end)) {
            int color = paper[start.row][start.col];
            paperCount[color] += 1;
            return;
        }

        Location middle = new Location((start.row + end.row) / 2, (start.col + end.col) / 2);
        devidePaper(start, middle); // 좌상
        devidePaper(new Location(start.row, middle.col + 1), new Location(middle.row, end.col)); // 우상
        devidePaper(new Location(middle.row + 1, start.col), new Location(end.row, middle.col)); // 좌하
        devidePaper(new Location(middle.row + 1, middle.col + 1), end); // 우하
    }

    public int getWhitePaperCount() {
        return paperCount[0];
    }

    public int getBluePaperCount() {
        return paperCount[1];
    }

    public boolean checkAllColorSame(Location start, Location end) {
        int color = paper[start.row][start.col];

        for (int i = start.row; i <= end.row; i++) {
            for (int j = start.col; j <= end.col; j++) {
                if (color != paper[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }
}

class Location {
    public int row;
    public int col;

    public Location(int row, int col) {
        this.row = row;
        this.col = col;
    }
}