[Java]伯俊9095号[1.2.3加]Java


百俊9095号です.
https://www.acmicpc.net/problem/9095

質問する


整数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の和を表す方法数を出力する.

    入力例

    3
    4
    7
    10

    サンプル出力

    7
    44
    274

    考える


    この問題はダイナミックプランニングで解いたものだ
    より正確には、Memoizationを使って解いたのです.
    Memoization[]配列を作成し、次の小さな問題を上に向かって大きな問題を解決する方法を選択します.

    アクション


  • 		int T = Integer.parseInt(br.readLine());
    		int memoization[] = new int[11];
    		
    		memoization[1] = 1;
    		memoization[2] = 2;
    		memoization[3] = 4;
    まず、テストケースの値を受け入れる変数Tを作成します.memoization[]配列で、ここでは、1と2、3は3つの数字で数字を生成する必要があるので、この1、2、3の組み合わせについて記録しました.
    数字4の場合、組み合わせの場合の数字は7で、この組み合わせは
    1の組合せ数、2の組合せ数、3の組合せ数を加算します.
    すなわち,このような方法で問題を解決すれば,我々は大数に類似した方法で繰り返す.
    次から問題を解決すればいいです.

  • 		while(T--> 0) {
    			int num = Integer.parseInt(br.readLine());
    			
    			if(memoization[i] == 0) {
    				memoization[i] = memoization[i - 1] + memoization[i - 2] + memoization[i - 3];					
    			}
    			else {
    				continue;
    			}
    
    			sb.append(memoization[num]+"\n");
    前述したように、必要な数値の組合せ数を表示するには、その結果値を格納できるmemoization[]配列に格納します.
    この値に達すると、
    StringBuilderに貼り付けて保存し、結果値を出力します.

    コード#コード#

    import java.io.*;
    
    public class Main {
    	
    	public static void main(String[] args) throws Exception {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		StringBuilder sb = new StringBuilder();
    		
    		int T = Integer.parseInt(br.readLine());
    		int memoization[] = new int[11];
    		
    		memoization[1] = 1;
    		memoization[2] = 2;
    		memoization[3] = 4;
    		
    		while(T--> 0) {
    			int num = Integer.parseInt(br.readLine());
    			
    			if(memoization[i] == 0) {
    				memoization[i] = memoization[i - 1] + memoization[i - 2] + memoization[i - 3];					
    			}
    			else {
    				continue;
    			}
    
    			sb.append(memoization[num]+"\n");
    		}
    
    		System.out.println(sb);
    	} // End of main
    } // End of class