[분할정복][JAVA] 4779번 : 칸토어 집합

문제

칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로,

구간 [0, 1]에서 시작해서 각 구간을 3등분하여

가운데 구간을 반복적으로 제외하는 방식으로 만든다.

 

전체 집합이 유한이라고 가정하고,

다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자.

 

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

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

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

예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다.

 

모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.

입력

입력을 여러 줄로 이루어져 있다. 각 줄에 N이 주어진다.

파일의 끝에서 입력을 멈춘다. N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.

출력

입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.

주어진 입력에 따라 칸토어 집합 길이 계산 

 

1. 3등분해서 가운데 제거 

2. 재귀적, 분할적복 이용해서 계속해서 반복 

3. 조건 : 하나 남을 때까지 한다. 

 

 

--------- (n이 3인 경우)
// 칸토어 집합 생성
1. 중간 부분을 먼저 공백으로 바꾸어 줍니다.
---   ---
2. 첫번째 부분을 DFS 함수를 통해 중간 부분만 공백으로 바꾸어줍니다.
- -   ---
3. 만약 전체 길이가 3보다 작으면 RETURN 합니다.
//전체 길이가 3보다 작다 -> - - 이렇게 되어있다.-> -한개만 남는다. -> 끝조건
4. 세번째 부분을 DFS 함수를 통해 중간 부분만 공백으로 바꾸어줍니다.
- -   - -

import java.io.*;

//Main따로 있고
public class Main{
    //Main에 들어갑니다.
    //char입니다.
    static char c[];
    static int N; 
    
    //main따로 있고
    public static void main(String args[])throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    	//str 빼먹음
        String str;
        //readLine할 때 str에 넣어줌
        //null이 아닌 동안에
        //괄호 두개 쳐야함
        while((str=br.readLine())!=null){
            N=Integer.parseInt(str);
            int cnt = (int)Math.pow(3,N); //27
            //char 크기 지정해줍니다.
            //char 써야함
            c=new char[cnt]; 
            for(int i=0;i<cnt;i++) c[i]='-';
        
        	//dfs안에 cnt이다.
            dfs(0,cnt);
            for(int i=0;i<cnt;i++) bw.write(c[i]);
            //" "쓰십시오
           
            bw.write("\n");
            bw.flush();
        } 
    }

    //반환형 적어줘야함, 접근 가능하게 static 붙여줘야함 length임
    static void dfs(int start, int length){
        //재귀 탈출 if문 넣어줘야지
        //만약 전체 길이가 3보다 작다면 return
        if(length<3){
            return;
        }
    
        //가운데에 빈칸 넣어주기
        for(int i=start+length/3;i=start+length/3*2;i++) c[i]=' ';
    
        //첫번째, 세번째 확인하기
        //전체 길이는 3분의 1이 된다 둘다
        dfs(start, length/3);
        dfs(start+length/3*2, length/3);
    }
 
}

 

참고 블로그 : 

https://dang2dangdang2.tistory.com/196

[JAVA]백준_4779_칸토어집합

 

 

 

 bw.write("\n");

띄어쓰기 할 때 \이거 쓴다. 하

 

 

2023-05-14 (2solve)

 

2023-05-15(3solve) _ main 앞에 public 빼먹고 cnt 앞에 int 안써줌

 

2023-05-16(4solve)_ char 배열이고, dfs(0, cnt)이다. ㅠㅠ