[JAVA]백준_4779_칸토어집합

문제링크

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

4779번: 칸토어 집합

 

 

코드 중간에 설명적어놨습니다.

 

저는 재귀로 풀었습니다.

--------- (n이 3인 경우)

1. 중간 부분을 먼저 공백으로 바꾸어 줍니다.

---   ---

2. 첫번째 부분을 DFS 함수를 통해 중간 부분만 공백으로 바꾸어줍니다.

- -   ---

3. 만약 전체 길이가 3보다 작으면 RETURN 합니다. 

 

4. 세번째 부분을 DFS 함수를 통해 중간 부분만 공백으로 바꾸어줍니다.

- -   - -

 

이렇게 완성이 됩니다.

 

 

System.out.println 쓰면 시간 초과가 나서 BufferedWriter로 해결했습니다.

 

 

package BOJ;

import java.io.*;

public class Main_4779 {
    static int N;
    static char c[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str;
        while((str = br.readLine()) != null){ //입력이 없을 때 까지 ㄱㄱ
            N = Integer.parseInt(str); //N

            int cnt = (int) Math.pow(3,N); //3의 N 제곱 구하기
            c = new char[cnt]; //char 배열 생성

            for(int i=0;i<cnt;i++) c[i] = '-'; //char배열에 - 로 채워주기

            dfs(0,cnt);

            for(int i=0;i<cnt;i++) bw.write(c[i]);
            bw.write("\n");
            bw.flush();
        }
    }

    static void dfs(int start,int length){
        if(length < 3) {
            return;
        }

        //중간꺼 공백으로 바꾸고
        for(int i=start+length/3;i<start+length/3*2;i++) c[i] = ' ';


        //첫번째거 세번째꺼 확인
        dfs(start,length/3);

        dfs(start+length/3*2,length/3);
    }
}