[JAVA] 백준 4779 칸토어 집합

4779번: 칸토어 집합 (acmicpc.net)

4779번: 칸토어 집합

 

- 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0,1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다

 

1. - 가  3N개 있는 문자열에서 시작한다.

2. 문자열을 3등분  한 뒤, 가운데 문자열을 공백으로 바꿈, 이렇게 하면 선(문자열) 2개가 남는다.

3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속한다.

 

- N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램 

 

 

풀이 과정 

 

- n번째 칸토어 집합은 n-1 번째 칸토어 집합을 2개 이은 것

- 중간에 공백이 n-1번째 칸토어 집합의 크기만큼 존재 해야 함 

- n번째 결과 = n-1번째 결과 + n-1번째 결과 길이만큼의 공백 + n-1번째 결과 

 

[C++] 백준 4779번 칸토어 집합 (tistory.com)

[C++] 백준 4779번 칸토어 집합

 

 

정답

 

import java.util.Scanner;

public class Main {
	
	public static String cantor(int n)
	{
		int size = (int)Math.pow(3, n-1);
	    StringBuilder s = new StringBuilder();
		
		if(n==0)
		{
			return "-";
			
		}
		
		s.append(cantor(n-1));
		for(int i=0; i<size;i++)
		{
			s.append(" ");
			
		}
		s.append(cantor(n-1));	
		
		return s.toString();
	}
	
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        
        int n;
        
        while(sc.hasNext())
        {
        	n = sc.nextInt();
        	System.out.println(cantor(n));
        }
    }
}