2448번 - 별 찍기 - 11

1️⃣ 재귀

 

✏️ 풀이 과정

프랙탈 도형을 만드는 문제입니다. 풀이를 위해서는 두 가지 요소가 필요한데 하나는 정확히 어떤 도형이 반복되는지 기준을 잡아야 한다는 것이고 다른 하나는 어떤 방식으로 다음 단계의 도형이 만들어지는 지 규칙을 알아야 합니다.

 

결론적으로 말하자면 반복되는 도형은 삼각형 모양의 최초의 별 6개로 시작하는 도형이고 다음 단계 도형의 규칙은 현재 단계 도형 2개를 아래에 붙여 새로운 삼각형을 만드는 것입니다.

 

재귀로 이를 구현할 때 가장 문제가 되는 부분은 도대체 삼각형 중간의 빈 공간을 어떻게 계산해서 메워야하는지 일텐데요, 삼각형을 그대로 삼각형이라고 생각하기보다는 공백까지 포함해서 직사각형을 반복한다고 생각하는 쪽이 편리합니다.

 

위 방법대로 로직을 구현하면 우선 1단계 삼각형을 String ArrayList에 저장하고(나중에 String.join메서드를 이용해 한 번에 이어붙입니다.) 다음 단계를 계산할 때 1단계 삼각형을 아래 한 칸 공백을 두고 두 번 붙여넣고, 1단계 삼각형 양쪽에 공백(1단계의 사이즈와 같습니다.)을 더해서 새로 변경된 직사각형을 얻을 수 있습니다.

 

이를 통해서 각 단계의 도형을 얻을 수 있는데 남은 것은 주어지는 숫자와 단계의 연관성을 찾는 것입니다. N의 식은 문제에서 주어지기 때문에 이를 고려해서 계산해보면 N이 주어졌을 때 거쳐야 하는 단계 수는 log_2(N/3)과 같습니다. Java에서 log_2 메서드가 주어지지 않기 때문에 밑변환 공식을 이용해서 log_2(N/3)의 값을 계산했습니다.

 

⏱ 시간 복잡도

각 단계마다 사이즈가 2배로 들어나기 때문에 전체 연산 횟수는 3 + 6 + 12 + ... + 3 x 2^N과 같고 등비급수의 합과 같기 때문에 시간 복잡도는 O(2^N)이 됩니다.

 

💻 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main{
	
	static int N;
	static ArrayList<String> strs;
	
	static void make(int n) {
		if(n == N) {
			return;
		}
		
		int size = strs.size();
		StringBuilder sb = new StringBuilder();
		String cur;
		for(int i=0;i<size;i++) {
			sb.append(" ");
		}
		for(int i=0;i<size;i++) {
			cur = strs.get(i);
			strs.add(cur+" "+cur);
			strs.set(i, sb+cur+sb);
		}
		make(n+1);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = (int) (Math.log10(Integer.parseInt(br.readLine()) / 3) / Math.log10(2));
		strs = new ArrayList<>();
		strs.add("  *  ");
		strs.add(" * * ");
		strs.add("*****");
		make(0);
		System.out.print(String.join("\n", strs));
		br.close();
	}
}