백준 9461번: 파도반 수열

 

보자마자 뭔가 규칙이 있을 것 같았고, 그 규칙을 찾아서 DP로 풀어야겠다고 생각이 들었다.

뭔가 P(N)은 P(N-1) + P(N-m)의 합으로 만들어 지는것 같았다. m이 무엇인지 알기위해 일일히 손으로 써보았다.

P(N)을 배열로 나타내보면 아래와 같다

인덱스	1	2	3	4	5	6	7	8	9	10	11
P(N)	1	1	1	2	2	3	4	5	7	9	12

3 = 2 + 1
p(6) = p(5) + p(1)

4 = 3 + 1
p(7) = p(6) + p(2)

5 = 4 + 1
p(8) = p(7) + p(3)

7 = 5 + 2
p(9) = p(8) + p(4)

9 = 7 + 2
p(10) = p(9) + p(5)

12 = 9 + 3
p(11) = p(10) + p(6)

그 결과 아래와 같은 식을 도출할 수 있었다.

p(n) = p(n-1) + p(n-5)

n의 입력값이 최대 100이므로 크기가 100이고 P(N)이 모두 계산되어있는 배열을 만들면 편할 것 같다.

package Test;

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder st = new StringBuilder();

		// DP배열 미리 생성
		long p[] = new long[101]; // int형의 최대 값을 넘어서므로 long형으로 선언
		p[0] = 0;
		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];
		}

		// TestCase 입력
		int t = Integer.parseInt(br.readLine());
		for (int i = 0; i < t; i++) {
			// n값 입력
			int n = Integer.parseInt(br.readLine());
			st.append(p[n] + "\n"); // 완성된 dp배열에서 n번째 인덱스 출력
		}

		// 출력
		bw.write(st.toString());
		bw.flush();
		bw.close();
	}
}