한 줄 요약
작은 부분에서 시작하여 큰 부분을 완성해서 답을 구하는 bottom-up 방식의 풀이와 큰 부분에서 시작해서 작은 부분을 구하는 top-bottom 방식 풀이 모두에 익숙해질 필요가 있다.
문제 설명
•
문자열의 길이가 주어지면, 길이가 1이 될 때까지 -, , - 형태로 바꾸는 문제
예제 입력/출력
•
입력1
0
1
3
2
Python
복사
•
입력1
-
- -
- - - - - - - -
- - - -
Python
복사
제약 조건
•
문제 풀이
[풀이1] bottom-up 방식
시간 복잡도:
접근 방식
•
재귀함수를 사용하지 않고 bottom-up 방식으로 문제를 해결할 수도 있다.
일 때와 일 때의 관계를 파악하여 답을 구하면 된다.
ans[i] = 입력이 i일 때의 답 (문자열)
ans[i] = ans[i-1] + 공백이 3^(N-1)
Python
복사
•
양끝 = 문자열과 문자열끼리의 덧셈을 이용
•
공백 = 문자열의 곱셉을 이용
시간 복잡도 계산
•
제약 조건:
•
우리가 구해야하는 것: ans[0] ~ ans[12]
◦
ans[i]의 길이 =
◦
•
약 80만회 연산이 필요하므로 시간 안에 풀 수 있음
[풀이2] 재귀함수 이용
시간 복잡도:
•
문자열을 3등분하며 재귀적인 과정을 거치므로, 재귀함수를 이용하여 구현하면 된다.
문자열의 길이가 1이 되면 더 이상 쪼갤 수 없으므로 이 때를 Base Case로 하면 된다.
◦
즉, k=0일 때 Base Case
시간 복잡도 계산
•
하나의 깊이가 내려갈 때 3개씩 나눠지므로,
풀이 코드
풀이1 : bottom-up 방식
풀이2 : 재귀함수 이용