백준 9095 1, 2, 3 더하기

문제 링크: https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

주어진 숫자 n을 1, 2, 3의 합으로 표현할수 있는 방법의 수를 구하는 문제이다.

int 값을 리턴하는 재귀함수를 이용하여 구현했다.

#include <bits/stdc++.h>
using namespace std;
 
int t, n;
 
int solve(int sum) {
    int ret = 0;
    if(sum > n) return 0;
    if(sum == n) return 1;
 
    for(int i = 1; i <= 3; i++) {
        ret += solve(sum + i);
    }
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> t;
    while(t--) {
        cin >> n;
        cout << solve(0) << '\n';
    }
 
    return 0;
}
 

void형 재귀함수를 이용해서도 구현해봤다.

#include <bits/stdc++.h>
using namespace std;
 
int t, n, ans;
 
void solve(int sum) {
    if(sum > n) return;
    if(sum == n) ans++;
 
    for(int i = 1; i <= 3; i++)
        solve(sum + i);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> t;
    while(t--) {
        cin >> n;
        ans = 0;
        solve(0);
        cout << ans << '\n';
    }
 
    return 0;
}