[백준] 1780 종이의 개수(Java)

백준 - 1780 종이의 개수

풀이

분할 정복

1. 현재 size의 종이가 num으로 이루어졌는지 확인
   1-1. num으로만 이루어져있으면 true
   1-2. 그렇지 않으면 false
2. 각 num으로 이루어진 종이의 수 저장
   2-1. result[3] = { -1로 이루어진 종이의 수, 0로 이루어진 종이의 수, 1로 이루어진 종이의 수 }
3. size를 9개로 나눠서 재귀호출
   ➡️ row, col 을 3으로 나눈 인덱스에 접근

코드

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

public class NumberOfPaper {
	public static int[][] paper;
	public static int[] result = new int[3];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int size = Integer.parseInt(br.readLine());
		paper = new int[size][size];
		for (int i = 0; i < size; i++) {
			String[] paperStr = br.readLine().split(" ");
			for (int j = 0; j < size; j++) paper[i][j] = Integer.parseInt(paperStr[j]);
		}
		partition(0, 0, size);
		for (int r : result) System.out.println(r);
	}

	private static void partition(int row, int col, int size) {
		if (checkNum(row, col, size)) {
			result[paper[row][col] + 1] += 1;
			return;
		}
		int div = size / 3;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				partition(row + div * i, col + div * j, div);
			}
		}
	}

	private static boolean checkNum(int row, int col, int size) {
		for (int i = row; i < row + size; i++) {
			for (int j = col; j < col + size; j++) {
				if (paper[row][col] != paper[i][j]) return false;
			}
		}
		return true;
	}
}