#4779 : 칸토어 집합

풀이방법

사용된 것:

분할 정복

재귀

 

2022.05.19

전체가 '-'로만 채워진 문자열을 먼저 만들고, 함수 f가 특정 부분을 지우는 식으로 해결한다.

 

재귀적으로 정의된 함수 f는 다음과 같이 동작한다.

 

1. 주어진 문자열을 세 부분으로 동등하게 쪼갠다.
2. 주어진 문자열의 가운데는 지운다.
3. 주어진 문자열의 왼쪽과 오른쪽에 대하여는 재귀를 한다. 따라서 갈수록 더 짧은 부분에 대하여 재귀를 해나가게 된다.
4. 주어진 문자열의 길이가 1이 되었을 때가 base case이다. 이때 재귀를 종료한다.

코드

Java(2022.05.19)

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

public class Main {
	
	static char[] str;	//전체 문자열
	//문자열의 일정 부분에 대하여 재귀하는 함수 f
	static void f(int start, int len) {	//start는 이번에 다룰 부분의 시작 인덱스, len은 해당 부분의 길이
		if(len>1) {
			int next = len/3;	//주어진 문자열 길이의 1/3을 구해놓기
			
			//가운데 1/3을 지우기
			for(int i = 0; i<next; i++) str[start+next+i] = ' ';
			
			//왼쪽 1/3과 오른쪽 1/3에 대하여 재귀
			f(start, next);
			f(start+next+next, next);
		}
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = null;
		
		while((input = br.readLine()) != null) {
			int n = (int)Math.pow(3, Integer.parseInt(input));
			//'-'로만 이루어진 문자열 생성
			str = new char[n];
			Arrays.fill(str, '-');
			//재귀적으로 지우기
			f(0, n);
			//정답 출력
			System.out.println(str);
			
		}
		

	}

}