[백준] 4779 칸토어 집합 - 분할정복 + 재귀 JAVA

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

4779번: 칸토어 집합

코드설명

재귀를 활용한 분할정복 문제입니다.

 

문제로직입니다.

1. 문제에서 핵심은, 2번째 별을 찍을때 해당 공간은 빈공간으로 처리해야합니다.

여기서 2번째 별이란, '- -' 이런식으로 찍었을떄 가운데공간을 의미합니다. '- -   - -' 이것도 같은 의미입니다.

2. 빈공간이 찍히는 flag인 emptySpace를 매개변수로 함꼐 보내어 빈공간찍을때와 아닐떄를 구분합니다.

3. size가 1 이라면 더이상 분리할 수 없으므로 ' -' 을 찍습니다. 이를 통해 2번쨰 공간 이외에는 모두 '-' 를 찍을 수 있습니다.

코드

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

public class Main {
	public static int N;
	public static char[] arr;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	String input = "";
    	while( (input = br.readLine()) != null ) {
    		N = Integer.parseInt(input);
    		arr = new char[(int)Math.pow(3, N)];
    		divideConquer(0, arr.length, false);
    		for(int i=0;i<arr.length;i++) {
    			sb.append(arr[i]);
    		}
    		sb.append("\n");
    	}
    	
    	System.out.println(sb.toString());
    }
	
	public static void divideConquer(int index, int size, boolean emptySpace) {
		if(emptySpace == true) {
			for(int i=index; i<index + size; i++) {
				arr[i] =' ';
			}
			return ;
		}
		
		if(size == 1) {
			arr[index] = '-';
			return ;
		}
		
		int nSize = size / 3;		
		int count = 0;
		for(int i=index;i<index+size;i+=nSize) {
			count += 1;
			if(count == 2) { //2번쨰 공간은 빈공간이다.
				divideConquer(i, nSize, true);
			}
			else {
				divideConquer(i, nSize, false);
			}
		}
		
	}
	
}