4779 칸토어 집합

4779 칸토어 집합 / c++ / Silver3 / 10분

문제 및 코드

접근 방식

분할 정복 / DP

1. 문제를 보니 바로 생각이 난 것이, 선형 점화식 이었다. Ansewr[N] = Answer[N-1] + N길이의 공백 + Answer[N-1]
2. 그대로 적용했더니 풀렸다.

다시 생각해 볼 점

1. 처음에는 DP 필요한 경우만 계산하려고 했다.
2. 그런데 N을 계산하기 위해서는 무조건 N-1을 계산해야하는 구조였다. (선형)
3. 그래서 그냥 N=0~12까지의 결과를 모두 계산해줬다. (하지만 N이 작아서 시간 복잡도는 0ms가 나왔다)
4. 재귀의 영어 스펠링을 확인하려고 Recursion을 검색했는데 재밌는 이스터 에그를 발견했다. 궁금하신 분은 구글에 Recursion을 검색해보길 추천한다.