[백준][C] 11726번 2×n 타일링 (동적 계획법)

2xn 타일링 문제

가로 크기가 n인 곳을 채워야 할 때, 처음 타일을 세워서 놓는 경우 가로의 크기가 (n-1) 인 곳을 채우는 문제가 되고, 반대로 눞혀서 놓을 땐 (n-2) 곳을 채워야하는 문제가 된다. 이를 이용하여 점화식을 세우면 D[i] = D[i - 1] + D[i -2]가 되고 해당 문제를 푸는 방식은 재귀함수를 이용하거나 동적 계획법을 이용하면 풀 수 있다. 하지만, 실험해본 결과 재귀함수를 이용하여 제출하면 시간 초과의 결과가 나온다. 재귀함수를 이용하더라도 메모제이션을 사용한다면 통과할 수 있을 것 같긴하다!

또한 주의해야할 것이 처음의 풀이는  D[i] = D[i - 1] + D[i -2]를 저장하고 나중에 출력할 때 D[n]를 10007로 나누었는데 그렇게 하면 오버플로우가 나는지 오답이라고 뜨니! 저장할 때부터 D[i] = (D[i - 1] + D[i -2]) % 10007 로 저장해야 통과할 수 있다.

 

전체 성공 코드

#include <stdio.h>

int recursive(int n) {
    if (n == 1) {
        return 1;
    }
    
    if (n == 2) {
        return 2;
    }
    return (recursive(n - 1) + recursive(n - 2)) % 10007;
}

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

int main()
{
    int n;
    scanf("%d", &n);
    int ans = dp(n);
    printf("%d", ans);
}

결과 화면