[백준] 11727번 : 2xn 타일링 2 [C/C++]

#문제

11727번: 2xn 타일링 2

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

11727번: 2×n 타일링 2

 

---

#접근방법

동적계획법으로 접근하였다.

https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-11726%EB%B2%88-2xn-%ED%83%80%EC%9D%BC%EB%A7%81-CC

[백준] 11726번 : 2xn 타일링 [C/C++]

이 문제에서 약간 변형된 문제이다.

반응형

---

#풀이

#include <stdio.h>

int dp[1005]={1,1};

int main(){
    int n;

    scanf("%d",&n);

    for(int i=2;i<=n;i++)
        dp[i] = (dp[i-1] + 2*dp[i-2])%10007;

    printf("%d\n",dp[n]);

    return 0;
}

 

이 문제는 위에 링크된 2xn 타일링 문제에서 약간 변형된 문제이다.

 

달라진 점은 1x2, 2x1타일에서 2x2타일이 추가 된 것이다.

 

따라서 2xn의 직사각형에서 가장 왼쪽에 채울 수 있는 경우의 수는 1x2 타일 2개, 2x1타일 1개, 2x2타일 1개이다.

 

각각 타일들을 채우면 오른쪽 공간에는 2x(n-2), 2x(n-1), 2x(n-2)의 공간이 남을 것이다.

 

이 3가지 경우의 수를 더하는 경우의 수를 식으로 세우면 dp[i] = dp[i-1] + 2*dp[i-2] 가 된다.

 

10007로 나눈 경우의 수를 구하라고 했으니 dp[i] = (dp[i-1] + 2*dp[i-2])%10007로 반복문을 돌려준다.

 

dp[n]을 출력하면 정답이다.

---

#성능

---

#정리

동적계획법으로 풀어야 한다는 것,

 

경우의 수를 식으로 만들 수 있으면 풀 수 있는 문제였다.