백준 9461 (파도반 수열) - java

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

9461번: 파도반 수열

1, 1, 1, 2, 2, 3, 4, 5, 7, 9 -> 해당 수열의 규칙을 찾을 수 있는가가 주요 키포인트이다.

1,1,1,2,2를 고정적으로 주어지는 초기값이라 생각하자 즉 해당 문제는 dp[5]까지의 값이 초깃값이다.

dp[6]이상 부터는 dp[i] = dp[i-1] + dp[i-5] 이다. 그리고 이거 정수 범위를 넘어가니 자바의 경우에는 BigInteger 클래스를 사용하자. 생각보다 이 클래스를 다룰줄 알면 쏠쏠한 경우가 많다. 

 

import java.io.*;
import java.math.BigInteger;

public class Main {
    static int n = 0;
    static BigInteger[] dp = new BigInteger[101];
    public static void main(String[] args) throws IOException {
        dp[1]=new BigInteger("1");dp[2]=new BigInteger("1");
        dp[3]=new BigInteger("1");dp[4]=new BigInteger("2");
        dp[5]=new BigInteger("2"); // dp[5] 까지가 초깃값
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        for(int k=1;k<=n;k++)
        {
            int num = Integer.parseInt(br.readLine());
            BigInteger result = find(num);
            bw.write(result+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    static BigInteger find(int num)
    {
        if(num<=5)
        {
            return dp[num];
        }
        else{
            for(int i=6;i<=num;i++)
            {
                dp[i] = dp[i-1].add(dp[i-5]); // 점화식 , 주석 너무 날먹인가 ㅋㅋ;;
            }
            return dp[num];
        }
    }
}