Dynamic 백준 알고리즘 자바 9461 ‘파도반 수열’ 문제풀이

Problem

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

Input
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

Output
각 테스트 케이스마다 P(N)을 출력한다.

Solution

점화식만 찾으면 되는데 그게 너무 쉬워서 왜 이 레벨인지 모르겠는.. 그런 문제! 그러나 입력값 n의 범위가 100까지 되는데, 그게 int 자료형으로는 커버가 안 되서 반드시 long타입을 써줘야 한다.

Code

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int tc = scan.nextInt(), n;
		
		for(int i = 0; i < tc; i++) {
			n = scan.nextInt();
			long[] dp = new long[n+1];
			dp[1] = 1;
			if(n >= 2) dp[2] = 1;
			for(int j = 3; j < n+1; j++)
				dp[j] = dp[j-2] + dp[j-3];
			System.out.println(dp[n]);
		}
	}
}