[백준] 11726번: 2xn 타일링 (Java)

1. 문제설명

2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 256MB

 

2. 접근 방식

• `dp[i]`는 `i` 길이의 직사각형을 채우는 방법의 수를 저장한다.
• `dp[1]`과 `dp[2]`의 초기값을 설정한다.
• 위 그림을 참고하면 `dp[i] = dp[i-1] + dp[i-2]` 점화식을 구할 수 있다.
• `dp[i]`를 저장할 때 오버플로우 방지를 위해 문제에서 주어지는 10,007로 나눈 값을 저장한다.
• 최종적으로 `dp[n]`을 구한다.

 

3. 최종 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 직사각형의 가로 길이

        // 문제에서 n의 최대값이 1000이므로 1001 크기의 배열 생성
        int[] dp = new int[1001];
        dp[1] = 1; dp[2] = 2; // 초기값 설정

        for(int i=3; i<=n; i++) {
            // 점화식을 통해 dp 배열 채우기
            dp[i] = (dp[i-1] + dp[i-2]) % 10_007;
        }

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