[백준/c++] 9095번 : 1,2,3 더하기

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

🌵 문제

🌵 풀이 1

• 6번째까지 직접 써보면서 규칙을 찾아보았다.
• 4번째 부터 f(n)=f(n-1)+f(n-2)+f(n-3) 규칙이 성립함을 찾았다.
• 각 테스트케이스 마다 n을 입력받고 ,func(n)에 해당하는 값을 리턴받아 출력 하였다.
• 이때, 이전 테스트케이스에서 이미 구한값이면 바로 리턴될 수 있도록 정답 배열인 answer[i]에 값이 들어와 있으면 건너뛰도록 하였다.
• 이 방식은 어쩌다 우연히 규칙을 발견한거라서 아래 재귀함수를 이용한 코드도 작성한다.

🌵 코드 1

//9095번: 1,2,3 더하기
#include <iostream>
using namespace std;

int answer[11];
int t,n;

int func(int n){
    if(n==1)
    return 1;
    if(n==2)
    return 2;
    if(n==3)
    return 4;

    for(int i=4; i<=n; i++){
        if(answer[i])
        continue;
        answer[i]=answer[i-1]+answer[i-2]+answer[i-3];

    }
    return answer[n];

}

int main(){
    answer[1]=1;
    answer[2]=2;
    answer[3]=4;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<func(n)<<"\n";

    }
    

}

🌵 풀이 2

• func(cnt, sum, goal)에서 cnt는 현재까지 더한 수의 갯수, sum은 현재까지 합계, goal은 만들고자 하는 수 이다.
• 1,2,3으로 구성되므로 for문을 돌면서 재귀함수에 더한값을 반영하여 현재까지의 합을 매개변수로 전달한다.
• sum이 만들고자하는 수를 넘어가면 goal을 만들 수 없는 조합이므로 리턴한다.
• answer은 goal을 만드는 방법이 수 이고, 각 테스트 케이스 초기에 answer=0 으로 초기화 한다.
• goal이 만들어지면 answer를 ++하고 리턴한다.

🌵 코드 2

//9095번:1,2,3더하기 - 재귀함수 이용
#include<iostream>
using namespace std;

int t,n;
int answer=0;
void func(int cnt, int sum, int goal){
    if(sum>goal)
    return;

    if (sum==goal){
        answer++;
         return;
    }

    for(int i=1; i<=3; i++){
        func(cnt+1,sum+i,goal);
    }
}
//cnt는 의미없어서 없애도 됨.

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>t;
    while(t--){
        cin>>n;
        answer=0;
        func(0,0,n); //cnt, sum의 초깃값은 0,0 이다.
        cout<<answer<<"\n";
    }

}