[11726] 2xN 타일링

🔗 문제 링크

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

🔍 문제 설명

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

⚠️ 제한사항

• $(1 ≤ n ≤ 1,000)$

• 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

🗝 풀이 (언어 : Java)

DP로 푸는 문제이다. DP는 아이디어를 생각하는 것이 쉽지 않은 문제인 것 같다. 이 문제도 마지막 타일을 1x2로 할지, 2x1로 할지로 나누어서 생각해볼 수 있다. 1x2, 2x1 마지막 타일을 제외하고 생각하면 n-2, n-1까지 만드는 경우의 수로 생각할 수 있다. $DP[i] = DP[i-2] + DP[i-1]$이 점화식이다. 주의할 점은 n이 1인 경우엔 dp배열을 n+1크기로 선언하면 인덱스 범위 오류가 뜨게된다. n+2 크기로 선언해주자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    private static int findCases(int n) {
        int[] dp = new int[n+2]; // n+1로 하면 n=1 일 때 dp[2]에서 인덱스 에러 발생
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)
            dp[i] = (dp[i-2] + dp[i-1]) % 10007;
        return dp[n];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();
        System.out.print(findCases(n));
    }
}