[伯俊][9095]1.2.3加-JavaScript

8762 ワード
テキストリンク

問題の説明


整数4を1、2、3の和と表す方法は全部で7種類ある.和を表すときは1つ以上の数を使います.
  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1
    • 整数nが与えられると、nが1、2、3の和で表される方法の数を求めるプログラムが作成される.

    入力


    第1行は、試験例の個数Tを与える.各試験例は1行からなり、整数nが与えられる.n은 양수이며 11보다 작다.

    しゅつりょく


    各試験箱、n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력.

    ［入力例1］

    3
4
7
10

    ［例出力1］

    7
44
274

    に答える



    n=4の場合、1로 시작했을 때는 3의 값을 조합하면 되는데 n=3일 때가 3을 조합할수 있는 모든 경우의 수であるため、これにより1から4を生成できる数を求めることができる.
    同様に、2で始まるときは、2の値を組み合わせればよいのですが、これは以前の値を利用すればよいのですが、3で始まるときも1の値を組み合わせるのですが、これも以前の値を利用した関係なので、配列で値を格納することで不要な計算を減らすことができます.
    このようにしてより大きな値n=10が得られると、dp[10]=dp[10−1]+dp[10−2]+dp[10−3]で得ることができる.

    最終コード

    const solution = (N, data) => {
    let answer = '';
    const dp = [0, 1, 2, 4];

    for (let i = 0; i < N; i += 1) {
        for (let j = 4; j <= data[i]; j += 1) {
            dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
        }
        const idx = data[i];

        if (i < N - 1) answer += `${dp[idx]}\n`;
        else answer += `${dp[idx]}`;
    }

    console.log(answer);
};

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0];
const data = [];
for (let i = 1; i <= N; i += 1) {
    data.push(+input[i]);
}

solution(N, data);
    Interface vs Abstract class
    アンプ＆バックエンド