[JAVA]백준_9461_파도반 수열

문제링크

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

9461번: 파도반 수열

 

 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			int N = sc.nextInt();
			long P[] = new long[N + 1];
			if (N >= 1)
				P[1] = 1;
			if (N >= 2)
				P[2] = 1;
			if (N >= 3)
				P[3] = 1;
			if (N >= 4)
				P[4] = 2;
			if (N >= 5)
				P[5] = 2;

			for (int i = 6; i <= N; i++) {
				P[i] = (P[i - 1] + P[i - 5]);
			}

			System.out.println(P[N]);
		}

	}
}

 

6번째 삼각형 부터

P(6) = P(5) + P(1)

P(7) = P (6) + P(2)

P(8) = P(7) + P(3) ...

이런식으로 규칙이 생긴다

 

따라서 P(N) = P(N-1) + P(N-5) 의 규칙이 생김으로 이걸 이용해서 풀어주면 된다.

근데 N 이 100일 경우 int의 범위를 벗어나므로 long으로 생성해주었다.