[DP/자바] 코드트리 IL. 사각형 채우기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

• 계단 오르기와 동일한 전형적인 DP 패턴
• 한 번에 1칸 오르냐 2칸 오르냐 하는 것
• n번째의 경우의 수를 구하는 것이니까 f(n) = f(n-1) + f(n-2);

문제 풀이

public class 사각형_채우기 {
    public static void main(String[] args) throws IOException {
        int[] dp = new int[1001];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= 1000; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(dp[n]);
    }
}