[BOJ] 4779 칸토어 집합

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

알고리즘 분류

• 분할 정복
• 재귀

풀이

• 재귀함수를 작성할 때는 무한 반복이 되지 않도록 유의해야 한다. 아래처럼 구획을 나누고 생각해보면 조금 더 쉽게 작성할 수 있다.
• 종료 시에 반환하는 값은 중간값이기도 하지만 결과값이기도 하기 때문에 결국은 결과값을 반환하는 코드를 써주면 된다.

returnType recursive(){
	// 종료 조건
    
    // 작업
    
    // 종료
    return value;
}

• 다음에 초점을 두고 코드를 작성했다.
  - 앞, 중간, 뒤 세 부분으로 나뉨
  - 앞과 뒤에 오는 문자가 동일함
  - 중간 부분은 공백 문자만 포함

    앞   /   중간  /   뒤   
- -   - -         - -   - -

Solution

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class baekjoon_4779 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder result = new StringBuilder();

    public static void main(String[] args) throws IOException{

        String line;
        // 입력이 종료될 때까지 받음
        while((line = br.readLine()) != null){

            int N = Integer.parseInt(line);
            
            String s = recursive(N, true);
            result.append(s).append('\n');
        }
        
        bw.write(result.toString());
        bw.flush();
        bw.close();
    }

    // b : 중간 배열-false, 양 끝-true
    public static String recursive(int N, boolean b){
        // 종료 조건
        if(b == false){
            StringBuilder s = new StringBuilder();
            for(int i = 0; i < (int) Math.pow(3, N); i++){
                s.append(" ");
            }
            return s.toString();
        }
        else{
            if(N == 0) return "-";
            // 종료
            return recursive(N-1, true) + recursive(N-1, false) + recursive(N-1, true);
        }
    }
}