백준 2630 색종이만들기

분할정복 기본문제

https://www.acmicpc.net/problem/2630

정말 간단해서 바로 메인로직

메인로직

1. 현재 주어진 사각형의 파랑 or 흰색 검사
2. 성공했다면 종료
   2.1 실패했다면 1/4로 쪼개서 분할정복진행 (이때 배열을 넘겨줘도 되고 좌표를 넘겨줘도됨)
3. 기저조건은 배열의 크기가 1이 되었을때 더이상 쪼갤수없으므로 넣어줌

import java.util.*;
import java.io.*;
public class 색종이 {

	static int N;
	static int array[][];
	static int banswer;
	static int wanswer;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		array = new int[N][N];
		banswer=0;
		wanswer=0;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		div(N,0,0);
		System.out.println(wanswer);
		System.out.println(banswer);
	}
	
	
	public static void div(int length, int i, int j) {
		if(length==1) {
			if(array[i][j]==0) wanswer++;
			else banswer++;
			return;
		}
		
		// 현재 사각형 검사
		int sum = 0;
		for(int a=i;a<i+length;a++) {
			for(int b=j;b<j+length;b++) {
				sum += array[a][b];
			}
		}
		if(sum==0) {
			wanswer++;
			return;
		}
		if(sum==length*length) {
			banswer++;
			return;
		}
			
		int ql = length/2;
		div(ql,i,j);	
		div(ql,i+ql,j);
		div(ql,i,j+ql);
		div(ql,i+ql,j+ql);
	};

}

빠르게 실2 실1로넘어가자 ㄱㄱㄱ