#9095. 1, 2, 3 더하기

순열을 이용해서 풀려고 했다가 결국 실패하고 찾아봤더니 재귀함수를 이용해서 풀 수 있는 아주 간단한 방법이 있었다..

방법

1, 2, 3으로 조합할 수 있는 모든 경우의 수를 돌면서 합이 일치하면 카운트를 늘려주는 방식

n = 3 이면 다음과 같이 4가지 방법이 있다.

cpp

#include <iostream>
#include <algorithm>

using namespace std;

int answer;

void f(int sum, int num) {

	// 합이 n보다 커지면 종료한다
    if (sum > num) return;
    // 합이 일치하면 카운트를 늘려준다
    if (sum == num) {
        answer++;
        return;
    }
    
    f(sum+1, num);
    f(sum+2, num);
    f(sum+3, num);
}

int main() {
    
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n;
    cin >> n;
    
    while(n--) {
        
        int num;
        cin >> num;
        
        answer = 0;

        f(0, num);
        
        cout << answer << "\n";
    }
}