[백준] 11726: 2 x n 타일링 JAVA

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

---

풀이과정

이 문제는 Dynamic Programming (DP)를 사용해서 푸는 문제이다.

 

풀이 핵심

1. 일단 타일이 늘어나면 이전 크기의 타일 왼쪽과 오른쪽에 세로로 2x1 타일을 놓는 방식을 사용할 수 있기 때문에 DP 문제라고 생각했다. (n=4라면 n=3에서 구한 타일 배치 방식의 왼쪽과 오른쪽에 세로 타일을 하나 추가하는 식)
2. 직접 타일을 그려보며 점화식을 찾았다 (아래 사진 참고)
3. 점화식을 사용하여 코드 구현

 

---

최종 코드

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

// The main method must be in a class named "Main".
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());
        int[] dp = new int[N+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= N; i++){
            dp[i] = (dp[i-1] + dp[i-2])%10007;
        }
        bw.write(String.valueOf(dp[N]));
        bw.flush();
    }
}