문제 출처 : https://www.acmicpc.net/problem/9095
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수?
브루트 포스를 해결하려면 우선 방법의 개수가 최대 몇 개까지 나오는지 알아야 합니다.
여기서는 모든 경우의 수는 3^n보다 작거나 같습니다.
최악의 경우 1이 n번 나올 수 있기 때문이죠.
즉, n ≤10이므로 $3^{20}$ = 49049
여기서 시간복잡도는 $O(3^N)$ 이 됩니다.
<aside> 💡 재귀함수를 사용하려면 기준을 하나 정해야 합니다.
위의 문제는 순서가 중요합니다.
위치에 몇가지의 수가 들어가는지 정하는 문제이기 때문이죠.
그러니 재귀함수의 기준으로 위치를 선택!
기준을 가지고 기준에서 뭘 할지 정해야하는데 뭘 하는지 정하는게 함수가 하는 역할입니다.