[백준/JAVA] 11726번 2xN 타일링 - DP

문제

2xN의 타일을 채워라

세로로 2칸, 가로로 2칸인 타일을 통해
2*N의 타일을 채우는 문제이다.

풀이

조건

1007로 나눈 나머지를 저장해야한다.

DP

미리 값을 저장해두고 원하는 값을 불러오면 된다.

점화식 설정

경우의 수를 모두 작성해보고 규칙을 찾아보면 앞의 2개의 합이 지금의 값과 같다.
따라서 점화식은
dp[n] = dp[n-1] + dp[n-2] 이다.
즉, 점화식 시작은 3부터 시작한다.

코드

제출 코드

import java.io.*;

class Main {

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

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

        if (n < 3) {
            bw.write(String.valueOf(n));
        } else {
            int[] dp = new int[n+1];

            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; i++) {
                dp[i] = (dp[i-1]% 10007 + dp[i-2]% 10007) % 10007;
            }
            bw.write(String.valueOf(dp[n]));
        }
        bw.flush();
    }
}