백준 2630번 - 색종이 만들기

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

2630번: 색종이 만들기

 

 

 

 

 

딱 봐도 재귀를 쓰는 분할정복 유형의 문제이다. 예전에 비슷한 문제를 푼 적이 있어서 금방 풀었다.

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

1780번: 종이의 개수

 

 

 

 

 

1. 재귀의 매개변수로 배열, 시작점의 좌표, 종이의 크기를 넣었다.

2. 재귀 메소드의 안에서 우선 모두 같은 숫자로 이루어져 있는지(같은 색의 종이인지) 확인을 해준다.

3. 같으면 종이 색에 따라 카운트를 올리고, 다르면 4개로 분할해서 각 시작점의 좌표값과 1/2로 종이의 크기를 매개변수로 넣어 재귀를 돌린다. 

 

 

 

 

 

코드

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

public class Main {
	static int white = 0;
	static int blue = 0;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[][] paper = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				paper[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		divide(paper, 0, 0, N);
		
		System.out.println(white);
		System.out.println(blue);
	}

	public static void divide(int[][] paper, int a, int b, int n) {
		if(isSame(paper, a, b, n)) {
			if(paper[a][b] == 0) {
				white++;
			}else {
				blue++;
			}
			return;
		}else {
			divide(paper, a, b, n / 2);
			divide(paper, a, b + n / 2, n / 2);
			divide(paper, a + n / 2, b, n/2);
			divide(paper, a + n / 2, b + n / 2, n/2);
		}
		
	}

	public static boolean isSame(int[][] paper, int a, int b, int n) {
		int num = paper[a][b];
		for(int i = a; i < a + n; i++) {
			for(int j = b; j < b + n; j++) {
				if(paper[i][j] != num) {
					return false;
				}
			}
		}
		return true;
	}
}

 

 

 

 

 

 

결과