[백준] 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]);

		}


	}

}