백준 16456 하와와 대학생쨩 하와이로 가는 거시와요~ (JAVA)

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

16456번: 하와와 대학생쨩 하와이로 가는 거시와요~

 

문제 유형: DP

 

 

문제 풀이

 

이렇게 노가다로 dp[i] = dp[i - 3] + dp[i - 1]의 점화식을 발견해 풀었다.

 

전체 코드

import java.io.*;
import java.util.*;


public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long dp[] = new long[50001];

        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;

        if(n>3){
            for(int i = 4;i<=n;i++){
                dp[i] = (dp[i-1] + dp[i - 3]) % 1000000009;
            }
        }
        System.out.println(dp[n]);
    }
}