[java] 백준 알고리즘 9461번 파도반 수열 풀이

다이나믹 프로그래밍 문제라는 것을 감안하고 시작!

이 문제는 종이에 몇 번 끄적이다보면 규칙을 찾을 수 있다.

P(10) 정도까지 만들어보겠다. 

P(5)까지는 규칙이 안 보여서 직접 대입했다.

해당 값(파도반 수열 P(?))이 나오는데 어떤 순서의 값들이 더해진걸까를 찾아봤다.

6번째부터는 바로 현재 삼각형의 한 변과 4번째 전에 그려진 삼각형의 한 변을 더 한 길이가

다음 삼각형의 한 변 길이가 됐다. 

그럼 현재의 삼각형 길이를 구하기 위해서는

P(i) = P(i-1) + P(i-5)라는 식이 적용할 수 있지 않을까?

앞에서 말했듯이 5번째까지는 규칙이 안 보였으니 6번부터 바로 시작하겠다.

P(6) == P(5) + P(1) --> 3 == 2 + 1

P(7) == P(6) + P(2) --> 4 == 3 + 1

P(8) == P(7) + P(3) --> 5 == 4 + 1

P(9) == P(8) + P(4) --> 7 == 5 + 2

P(10) == P(9) + P(5) -> 9 == 7 + 2

P() 식 안에 대입할 숫자의 범위도 크지 않으니 

미리 만들어 놓고 입력되는대로 바로 출력하면 되겠다.

* 풀이 소스

 
public class Baekjoon9461 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        long[] padobanSeq = new long[101]; // 파도반 수열
        padobanSeq[1] = 1;
        padobanSeq[2] = 1;
        padobanSeq[3] = 1;
        padobanSeq[4] = 2;
        padobanSeq[5] = 2;
        
        for(int i=6; i<padobanSeq.length; i++) { // 6번째부터 규칙이 성립
            
            padobanSeq[i] = padobanSeq[i-1] + padobanSeq[i-5];
        }
        
        int testCase = Integer.parseInt(st.nextToken());
        for(int j=0; j<testCase; j++) {
            st = new StringTokenizer(br.readLine());
            sb.append(padobanSeq[Integer.parseInt(st.nextToken())]+"\n");
        }
        bw.write(sb.toString());
        bw.flush();
        
    }    
}