[백준] 9461번 : 파도반 수열(JAVA)

재미있는 Dynamic Programming

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 14단계

 

동적 계획법 1의 카테고리에 포함되어 있는 문제이다.

 

문제의 항을 1번부터 쭉쭉 적어보면

 

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, ...

 

이런 형태로 나오게 되는데

 

여기서 P(n) = P(n-3) + P(n-2)라는 식을 구할 수 있다.

 

//그림을 그려 규칙을 구하면 P(n) = P(n-5) + P(n-1)의 점화식이 나온다.

 

주의할 점은 int로 배열을 선언하였을 때,

 

79번째 부터 int값의 범위가 넘어간다는 것이다.

 

그래서 나는 long으로 선언을 하였다.

 

100번 째 값은 888,855,064,897라는 값이 나오게 된다.

 

import java.util.Scanner;

public class Question_9461 {

	public static void Sequence(long[] P) {
		for(int i = 3; i < 100; i++) {
			P[i] = P[i-3] + P[i-2];
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int Test_Case = sc.nextInt();
		long[] P = new long[100];
		P[0] = 1;
		P[1] = 1;
		P[2] = 1;
		
		Sequence(P);
		
		for(int i = 0; i < Test_Case; i++) {
			int N = sc.nextInt();
			System.out.println(P[N-1]);
		}
	}
}

테스트 케이스의 숫자를 먼저 받고

 

수를 받으면서 배열에 추가를 하려는 방법을 생각해 보았지만

 

그냥 먼저 100개의 배열에 전부 값들을 구한 다음에 입력받자마자 값을 출력하는 것이

 

낫다고 판단해 그냥 한번에 값을 모두 구했다.