[백준/BOJ] 9461번 파도반 수열 (Java/자바) - DP

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

9461번: 파도반 수열

 

풀이

이 문제는 깊게 생각을 안 했다.

문제에 있는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 수열을 보자마자

arr[i] = arr[i-2] + arr[i-3] 의 점화식을 떠올렸다.

이를 dp배열을 생성하여 그대로 구현

(주의)

dp배열을 int형으로 선언 시 계산값이 오버플로우가 발생할 수 있음

long타입으로 선언할 것.

package dp;

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

public class BOJ_9461_파도반수열 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long[] dp = new long[101];
		dp[1] = 1L;
		dp[2] = 1L;
		dp[3] = 1L;
		for(int i=4; i<=100; i++) {
			dp[i] = dp[i-2]+dp[i-3];
		}
		int TC = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int tc=1; tc<=TC; tc++) {
			int now = Integer.parseInt(br.readLine());
			sb.append(dp[now]).append("\n");
		}
		
		System.out.println(sb.toString());
	}
}