[BOJ/DP] 백준 11726 - 2xn 타일링 / 11727 - 2xn 타일링 2 (Java)

11726 - 2xn 타일링

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

문제

2xn 크기의 직사각형 -> 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램

입력: n (1 <= n <= 1,000)
출력: 2xn 크기의 직사각형을  채우는 방법의 수 % 10,007

---

풀이

• `dp[i]`: 가로 길이 i를 완전히 채우는 경우의 수
• `dp[i] = dp[i - 1] + dp[i - 2]` => 예시 참고

 

• n = 1 -> 2x1 사각형 경우의 수: dp[1] = 1
  • 2x1
• n = 2 -> 2x2 사각형 경우의 수: dp[2] = 2
  • 2x1 2개/ 1x2 2개

---

예시

편의상 2x1을 세로, 1x2를 가로라고 했을 때

• n = 1
  • 세로 1개
• n = 2
  • 세로 2개
  • 가로 2개
• n = 3 
  • 세로 3개 = 세로 2개 + 세로 1개 
  • 가로 2개 + 세로 1개
  • 세로 1개 + 가로 2개
• n = 4
  • 세로 4개 = 세로 3개 + 세로 1개
  • 가로 2개 + 세로 2개 = 가로 2개 + 세로 1개 + 세로 1개
  • 세로 2개 + 가로 2개 = 세로 1개 + 가로 2개 + 세로 1개
  • 세로 2개 + 가로 2개
  • 가로 2개 + 세로 2개

=> (n - 1) + 세로 1개 / (n - 2) + 가로 2개

---

코드

import java.io.*;

// 2xn 타일링
public class boj_11726 {
    static final int MOD = 10_007;

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

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

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

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

        System.out.println(dp[n]);
    }
}

---

11727 - 2xn 타일링 2

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

문제

2xn 크기의 직사각형 -> 1x2, 2x1, 2x2 타일로 채우는 방법의 수를 구하는 프로그램

입력: n (1 <= n <= 1,000)
출력: 2xn 크기의 직사각형을  채우는 방법의 수 % 10,007

---

풀이

• `dp[i]`: 가로 길이 i를 완전히 채우는 경우의 수
• `dp[i] = dp[i - 1] + 2 * dp[i - 2] `

 

• n = 1 -> 2x1 사각형 경우의 수: dp[1] = 1
  • 2x1
• n = 2 -> 2x2 사각형 경우의 수: dp[2] = 3
  • 2x1 2개/ 1x2 2개/ 2x2 1개

---

코드

import java.io.*;

// 2xn 타일링 2
public class boj_11727 {
    static final int MOD = 10_007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] dp = new int[10001];
        dp[1] = 1;
        dp[2] = 3;

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

        System.out.println(dp[n]);
    }
}