[JAVA] 백준 9461번 【파도반 수열】

---

오늘의 알고리즘 문제는 너무 쉽게 해결해서 좋다..ㅎ 

 

문제를 보아하니, 어떤 수학적인 식이 존재할 것 같아 보이지는 않았다. 그래서 각 항의 값을 직접 적어보니 규칙을 바로 발견할 수 있었다.

 

dp[1] = 1

dp[2] = 1

dp[3] = 1

dp[4] = 2

dp[5] = 2

dp[6] = 3 ( 1 + 2)

dp[7] = 4  (1 + 3)

dp[8] = 5  (1 + 4)

dp[9] = 7  (2 + 5)

dp[10] = 8 (2 + 7)

dp[11] = 12 (3 + 9)

dp[12] = 16 ( 4 + 12)

 

적어내려가다보니, 저 빨간색으로 표시한 숫자들이 눈에 너무 띄었다.

 

dp[6]부터 dp[1]이 더해지기 시작한다는 사실을 알았다. 즉,

 

dp[1] = 1

dp[2] = 1

dp[3] = 1

dp[4] = 2

dp[5] = 2

dp[6] = 3 ( 1 + 2) = dp[6-5] + dp[5]

dp[7] = 4  (1 + 3) = dp[7-5] + dp[5]

dp[8] = 5  (1 + 4) = dp[8-5] + dp[5]

dp[9] = 7  (2 + 5) = dp[9-5] + dp[5]

dp[10] = 8 (2 + 7) = dp[10-5] + dp[5]

dp[11] = 12 (3 + 9) = dp[11-5] + dp[5]

dp[12] = 16 ( 4 + 12) = dp[12-5] + dp[5]

 

최종적으로 dp[i] = dp[i-5] + dp[i-1] 가 된다는 사실을 알았다.

 

그리고 dp 배열을 생성할때, int 배열로 생성하면 오버플로우가 발생할 수 있으므로 long 배열로 생성해야 한다는 것을 주의하자.

 

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.valueOf(br.readLine());
		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-5]+dp[i-1];
		}
		for(int i=1;i<=T;i++) {
			System.out.println(dp[Integer.valueOf(br.readLine())]);
		}

	}
}