[백준(Baekjoon)][자바(java)] 9461 : 파도반 수열 / 동적 계획법 1

 

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

9461번: 파도반 수열

 

* 풀이 방법

- 변의 길이를 나열해보았음

1	2	3	4	5	6	7	8	9	10	11
1	1	1	2	2	3	4	5	7	9	12
					+1	+1	+1	+2	+2	+3

수열의 6번째 수부터 5개 전의 수만큼 더해지는 규칙 발견

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

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