Bottom-Up 방식과 Top-Down방식 알아보기 (BOJ 4779)

문제

BOJ 4779 문제

1. -가 3N개 있는 문자열에서 시작한다.
2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.
3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.

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

---------------------------

여기서 가운데 문자열을 공백으로 바꾼다.

---------         ---------

남은 두 선의 가운데 문자열을 공백으로 바꾼다.

---   ---         ---   ---

한번 더

- -   - -         - -   - -

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

단, N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.

---

Bottom-Up 방식이란?

Bottom-Up 방식은 작은 부분에서 부터 시작해서 큰 부분을 완성한 후 답을 구하는 방식의 풀이법입니다.

해당 문제를 Bottom-Up 방식으로 풀이한다면 작은 부분인 N이 0인 경우부터 시작해 N이 12인 경우까지 전부 구하고 사용자가 입력한 N의 값에 맞게 구한 값을 출력하면 됩니다.

풀이

ans = ['' for _ in range(13)]
ans[0] = '-'
 
for i in range(1, 13):
	ans[i] = ans[i-1] + (' ' * (3 ** (i-1))) + ans[i-1]
 
while True:
	try:
		n = int(input())
		print(ans[n])
	except:
		break

시간 복잡도: $O(3^N)$​

Top-Down 방식이란?

Top-Down 방식은 큰 부분에서 부터 시작해서 작은 부분을 구하는 풀이 방식입니다.

해당 문제를 Top-Down 방식으로 풀이한다면 큰 부분인 특정 N번째의 문자열을 구하는 재귀함수를 작성한 뒤, 작은 부분으로 재귀함수의 N번째를 구하는 풀이를 진행할 수 있습니다.

풀이

def cantor(n):
	if n < 1:
		return '-'
	return f'{cantor(n-1)}{' ' * (3 ** (n-1))}{cantor(n-1)}'
 
while True:
	try:
		n = int(input())
		print(cantor(n))
	except:
		break

시간 복잡도: $O(3^N)$​