백준 9095 1,2,3 더하기 (재귀)

이전에 for문을 통해서 같은 문제를 풀었다.

for문은 재귀로 바꿀 수 있기 때문에 재귀로도 풀 수 있다.

for문은 10개를 만들어야 했지만, 재귀는 많은 코드가 필요없으므로 조금 더 간단하게 풀 수 있다.

 

재귀는

1.불가능한 경우

2.정답을 찾은 경우

3.다음 경우를 호출하는 경우

와 같은 3가지 경우로 나누어 풀어야 한다.

 

1,2,3을 선택할 수 있으므로 시간 복잡도는 O(3^n)이다.

 

자세한 설명은 아래 코드의 주석으로..

#include <iostream>
using namespace std;
 
int ans;
int n;
void solve(int sum) {
    //1, 2, 3 중에 더하는 거라서 n을 넘어갈 수도 있음. 그 경우를 처리해줘야 한다.
    if (sum > n) return;
    //n과 일치하면 경우의 수 1개 증가
    if (sum == n)ans++;
    //sum이 아직 n에 도달하지 않으면 1, 2, 3을 한 번 더 더해본다.
    solve(sum + 1);
    solve(sum + 2);
    solve(sum + 3);
}
 
int main(int argc, char** argv) {
    int t;
    cin >> t;
 
    while (t--) {
        cin >> n;
 
        ans = 0;//test case가 여러 개므로 재귀 들어가기 전 0으로 초기화한다.
        solve(0);
        printf("%d\n", ans);
    }
 
    return 0;
}