[백준] 1780번 : 종이의 개수

문제

-1, 0, 1로만 이루어진 가로, 세로의 길이가 3^n인 종이가 주어졌을 때

같은 숫자로만 이루어진 종이가 종류별로 몇 개인지 출력하라

 

접근 방식

현재 종이가 같은 숫자로만 이루어지지 않은 경우에는

종이를 9등분 하고 같은 숫자로만 이루어져 있을 때만

해당하는 종이의 카운트를 1씩 올려줘야 한다.

 

종이의 가로, 세로 길이는 3의 n제곱으로만 주어지기 때문에

같은 숫자로 이루어지지 않은 경우에는 3으로 범위를 나눠주면서

재귀를 계속해서 돌려주면 된다.

 

예를 들어 가로, 세로의 길이가 27이고, 해당 종이가 같은 숫자로만 이루어지지 않았으면

가로, 세로 길이가 9인 종이 9개로 나눌 수 있고

이 종이를 다시 3인 종이와 1인 종이로 나눌 수 있다.

 

나눌 때마다 현재 종이가 같은 숫자로 이루어진지 확인하고

일치한다면 해당 숫자의 카운트를 증가시키고

그렇지 않다면 다시 재귀를 호출한다.

 

길이가 1인 경우에는 더 이상 나눌 수 없기 때문에

이를 재귀 함수의 기저 조건으로 지정해 주면 된다.

 

풀이

public class Main {

	private static int[][] arr;
	static int minus = 0, zero = 0, plus = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		arr = new int[n][n];

		for (int i = 0; i < n; i++) {
			String[] inputs = br.readLine().split(" ");

			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(inputs[j]);
			}
		}

		count(0, 0, n);
		System.out.println(minus);
		System.out.println(zero);
		System.out.println(plus);
	}

	private static void count(int start, int end, int size) {
		if(equals(start, end, size)) {
			int num = arr[start][end];
			if(num == -1) {
				minus++;
			}
			if(num == 0) {
				zero++;
			}
			if(num == 1) {
				plus++;
			}
			return;
		}

		int newSize = size / 3;
		for (int i = start; i < start+size; i+= newSize) {
			for (int j = end; j < end+size; j += newSize) {
				count(i, j, newSize);
			}
		}
	}

	private static boolean equals(int start, int end, int size) {
		for (int i = start; i < start + size; i++) {
			for (int j = end; j < end + size; j++) {
				if(arr[start][end] != arr[i][j])
					return false;
			}
		}

		return true;
	}
}