[백준-11726번] 2×n 타일링 풀이 - Java

반응형

🚀 문제

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

 

🚀 접근 방법

DP 문제이다.홀수라면 이전에서 2x1 블럭 밖에 못붙는다.짝수라면 2X2 경우만큼 올 수 있다.따라서 점화식은 dp[i] = dp[i-1][i-2]가 된다.

 

🚀 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        final int MOD = 10007;

        int n = Integer.parseInt(in.readLine());


        int[] dp = new int[n+1];

        dp[1] = 1;
        if(n>=2)
            dp[2] = 2;

        for(int i=3; i<=n; i++){
            dp[i] = (dp[i-1]+dp[i-2])%MOD;
        }


        out.write(Integer.toString(dp[n]));

        out.flush();
        out.close();
        in.close();
    }
}