[伯俊/c++]9095号:1、2、3プラス

2393 ワード
復帰する ダイナミックプログラミング テキストリンク
質問リンク-https://www.acmicpc.net/problem/9095

🌵 質問する



🌵 答えを出す。


  • まで6回目に自ら試用し、ルールを探す.
  • の4回目から,f(n)=f(n−1)+f(n−2)+f(n−3)ルールの成立が見つかった.
    • 各テストボックス
  • は、n入力を受け入れ、func(n)の値出力を返す.
  • このとき、先のテストケースでは、得られた値をすぐに戻すために、正しい答え配列[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";

    }
    

}

    🌵 説明する。

  • func(cnt,sum,goal)では、cntはこれまで1つの数であり、sumはこれまでの総数であり、goalは作成したい数である.
  • 1、2、3からなり、for文の周りに再帰関数に加えられた値が反映され、これまでの和がパラメータとして伝達される.
  • sumが作りたい数を超えると、目標の組み合わせを作ることができないので、反撃します.
  • 解答作成ターゲットのメソッドは数であり、各テストケースの初期段階で解答を=0に初期化する.
  • 球をクリアした後、++と答えて返します.

    • 🌵 コード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";
    }

}
    useQueryがundefinedを返すときの一時的な方法!
    git stash