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

11727번 문제 설명

이전에 포스팅한 타일링 문제에서 약간의 변형이 된 문제이다.

soyoonique.tistory.com/46?category=807751

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

다른 점이 있다면 이전에는 (n - 2) 크기의 타일을 부르는 경우가 1 x 2 타일을 가로로 나란히 놓은 경우밖에 없지만, 이번에는 정사각형을 놓는 경우가 추가되었다는 것이다. 즉, 점화식은 D[i] = D[i - 1] + 2 * D[i -2]이 되고 이전과 동일한 방법으로 값을 채우면 된다. 

전체 성공 코드

#include <stdio.h>


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

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

결과 화면