[백준] 2630번 : 색종이 만들기

문제

위와 같이 그림의 색깔 (파란색:1, 흰색:0)의 정보가 주어질 때

한 가지 색깔로만 이루어진 그림의 종류가 각각 몇 개인지 출력하라

 

 

접근 방식

이전에 풀었던 1780번 문제와 같은 문제로

기존에 3으로 나누던 방식에서 2로 나눠주는 부분만 바뀌고

종이의 종류가 흰색과 파란색 두 개만 있다는 것만 다르다.

 

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

 

이전 글을 참고하면 좋다.

 

풀이

public class Main {

	private static int[][] arr;
	private static int[] count = new int[2];

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

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

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

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

		count(0, 0, n);

		sb.append(count[0]).append("\n");
		sb.append(count[1]).append("\n");

		System.out.println(sb);
	}

	private static void count(int start, int end, int size) {
		if (verification(start, end, size)) {
			if (arr[start][end] == 0) {
				count[0]++;
			} else {
				count[1]++;
			}

			return;
		}

		int newSize = size / 2;

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

	private static boolean verification(int start, int end, int size) { // 0 4 4
		int now = arr[start][end];

		for (int i = start; i < start + size; i++) {
			for (int j = end; j < end + size; j++) {
				if (now != arr[i][j]) return false;
			}
		}

		return true;
	}
}