[백준] 4779번 : 칸토어 집합

문제

 

 

접근 방식

기본적인 재귀 문제로 문제에 기저 조건부터 규칙까지 그대로 나와 있기 때문에

코드로 구현만 하면된다.

 

우선 재귀 함수의 기저 조건은 선의 길이가 1일 때일 것이고

현재 선의 중앙을 길이의 3분의 1만큼 공백으로 바꿔준 후에

나머지 왼쪽과 오른쪽 선도 재귀를 이용해 같은 과정을 반복해주면 된다.

 

풀이

public class Main {

	private static char[] chars;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		String input;

		while ((input = br.readLine()) != null) {
			int n = Integer.parseInt(input);
			int len = (int) Math.pow(3, n);

			chars = new char[len];

			for (int i = 0; i < len; i++) {
				chars[i] = '-';
			}

			solve(0, len);

			sb.append(chars).append("\n");
		}

		System.out.println(sb);
	}

	private static void solve(int s, int e) {
		if (e - s <= 1) return;

		int x = (e - s) / 3;

		for (int i = s + x; i < e - x; i++) {
			chars[i] = ' ';
		}

		solve(s, s + x);
		solve(e - x, e);
	}
}