[Java] 백준 9461번 (Dynamic Programming)

www.acmicpc.net/problem/9461

9461번: 파도반 수열

풀이

---

변의 길이가 1인 정삼각형에서 시작하여 변을 이어가며 정삼각형을 그리는 문제로

P(1) = 1, P(2) = 1, P(3) = 1, P(4) = 2, P(5) = 2 ... P(11) = 12까지 예시가 주어져있다.

 

위 규칙을 통해 P(N) = P(N-1) + P(N-5) 를 알 수 있다

P(1) ~ P(5)일 경우는 예외로 두고 N = 6일때부터 풀었다

 

cf) N이 100까지로 한정되어 있기때문에 이 범위가 int의 범위를 벗어나는지를 체크해보고 넘어가야 한다

 

import java.io.*;
import java.util.*;

//https://www.acmicpc.net/problem/9461
public class algo_9461_dp {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		long[] P = new long[101];
		P[1] = 1; P[2] = 1; P[3] = 1; P[4] = 2; P[5] = 2;
		
		for(int i = 6; i<= 100; i++) {
			P[i] = P[i-1] + P[i -5];
		}
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			bw.write(P[N] + "\n");
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}