백준 9461번 : 파도반 수열

 문제

www.acmicpc.net/problem/9461

9461번: 파도반 수열

9461 파도반 수열

 

 구현 방법

 점화식을 구해준 다음 dp로 구현하였습니다.



그림을 보면 점화식은 dp[i] = dp[i-2] + dp[i-3] 임을 알 수 있습니다.

 

 구현 코드

package BOJ.Silver;

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

public class BOJ9461_파도반수열 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int tc=0;tc<TC;tc++) {
			int N = Integer.parseInt(br.readLine());
			long[] dp = new long[N+1];
			dp[1]=1;
			if (N>1) dp[2]=1;
			if (N>2) dp[3]=1;
			for (int i=4;i<=N;i++) {
				dp[i] = dp[i-2]+dp[i-3];
			}
			sb.append(dp[N]+"\n");
		}
		System.out.println(sb);
	}
}

 

정답!