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

1. 문제설명

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

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

 

2. 접근 방식

• `dp[i]`에 가로 길이가 i일 때 채우는 방법의 수를 저장한다.
• `dp[i] = dp[i-1] + dp[i-2] * 2`
  

  

• `dp[1]`과 `dp[2]`는 초기값 설정하고, i=3 부터는 점화식을 사용해 값을 구한다.

 

3. 틀린 이유

`dp[i]` 에 값을 저장할 때 점화식 계산한 값을 그대로 넣었더니 데이터 타입을 초과해서 틀렸다.

 

 

4. 틀린 부분 수정

저장할 때 `% 10007` 연산으로 10007 이하로 값을 저장했다.

 

 

5. 최종 코드

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());

        int[] dp = new int[1001]; // dp 배열의 크기를 1001로 설정
        // 초기값 설정
        dp[1] = 1; // 2x1 직사각형을 채우는 방법의 수
        dp[2] = 3; // 2x2 직사각형을 채우는 방법의 수

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

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

 

6. 느낀점 or 기억할정보

dp 배열에는 문제에서 주어지는 최대값으로 크기 설정하기!

아직 점화식을 추출해내는 것이 어렵다..