[백준(Baekjoon)/JAVA] 2630. 색종이 만들기

 

2630번: 색종이 만들기

문제가 굉장히 길어서 링크 첨부.

 

 

 

이건 재귀함수를 이용해 풀어야 하는 문제다.

정사각형(근데 3*3은 안됨,2의 제곱수로만 됨)형태로 되어있는걸 세어야 함.

그게 색종이의 갯수임.

1로 표시된건 파란 색종이이고, 0으로 표시된건 하얀색종이이다.

4분할을 해서 거기서 파란정사각형과 하얀정사각형을 찾고 둘 다 없을 경우

다시 그것을 4분할하여 쪼개면서 찾아나간다.

큰 정사각형이 없어서 계속 쪼개다 보면 1*1인 정사각형까지 오게되고 거기서 끝남.

한번에 정사각형으로 찾으면 재귀 안들어가고 거기서 바로 끝남.

 

 

package bj;

import java.util.Scanner;

public class bj2630 {
	
	static int blue = 0;//파란 색종이 수
	static int white = 0;//하얀 색종이 수

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[][] arr = new int[n][n]; 
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		cnt(arr, 0, 0, n);
		System.out.println(white);
		System.out.println(blue);
	}
	
	public static void cnt(int[][] arr, int i, int j, int n) {
		
		int sum = 0;
		
		for(int k = i; k < i+n ; k++) {
			for(int h = j; h < j+n; h++) {
				sum += arr[k][h];//색종이가 1이면 1이 더해지고 0이면 0이 더해짐
			}
		}
		
		
		if(sum == n*n) {//사각형모양이 1로 가득 차있을 경우 : 파란 색종이
			blue++;
		}
		else if(sum == 0) {//사각형모양이 0으로 가득 차있을 경우 : 하얀 색종이
			white++;
		}
		else {//둘다 아닐 경우 그것을 다시 4분할
			n = n/2;
			cnt(arr, i, j, n);//왼쪽위
			cnt(arr, i+n, j, n);//오른쪽위
			cnt(arr, i, j+n, n);//왼쪽아래
			cnt(arr, i+n, j+n, n);//오른쪽아래
		}
	}

}

 

왜 정답률이 71퍼인지 이해가 잘 가지 않는 문제.

이전문제보다 더 어려움.

 

 

 

 

 

/0108