[伯俊]9461波の半数列(シルバー3)

白駿(シルバー3)-9461.波の半数列(銀色3)

に答える

波の半数列を羅列すると以下のようになります.
1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265,,,
4=2+2
5=3+2
7は3+4
9は4+5です.
これらの数字の羅列から,数字はi−3とi−2が加算されていることがわかる.
1828587033,-1872605217,-1086020751,-44018184,1336341328
,,,
ここで注意したいのは、83番目の数字にdummy値が表示されます.
数がint型の範囲を超えているためlong変数を使用する必要があります.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;

public class BOJ9461 {
	public static long[] numbers = new long[101];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		numbers[0] = 1;
		numbers[1] = 1;
		numbers[2] = 1;
		for(int i=3; i<101; i++) {
			if(numbers[i] ==0) numbers[i] = numbers[i-3]+numbers[i-2];
		}
		for(int t = 0; t<tc; t++) {
			int n = Integer.parseInt(br.readLine());

			System.out.println(numbers[n-1]);

		}


	}

}