백준 11726 자바 2xn 타일링

백준 11726번

11726번: 2×n 타일링

 

문제

---

 

 

풀이

---

 

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

public 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[1001];

        dp[1] = 1; // 2x1 로 하나 채우기
        dp[2] = 2; // 2x1로 || 1x2로 2가지 방법

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



        bw.write(dp[n] + "\n"); // 문자열 or 변수명+""
        bw.flush();  //버퍼 비우기  
        bw.close(); // 종료
    }
}

 

2x1의 경우 2x1타일 하나로 채우는 방법 한 가지만 있다.

2x2의 경우 2x1타일 2개, 1x2타일 2개 로 채우는 방법 2가지가 있다.

 

2x3을 2칸을 채우고 1칸을 채우는 것이므로 dp[1] + dp[2]라고 볼 수 있다.

해당 문제는 그려보면 이해가 빠르다. 

 

이런식으로 풀어나가면 된다.   

 

다이나믹 프로그래밍의 개념을 생각해보면 쉽게 풀 수 있는 문제이다.