[Boj] 백준 C++ #11726 2xn 타일링

📍알고리즘 분류: DP 동적 프로그래밍
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 경우 DP를 사용한다.

📍문제 풀이:
처음에는 조합(Combination)을 이용한 수식으로 문제에 접근했다. 문제에서 높이는 2로 고정되어 있으므로 2xn 타일을 쪼개보면 타일을 구성할 수 있는 경우는 '2x1' 혹은 '1x2 두개를 위아래로 붙인 2x2' 뿐이다. 그래서 2x1의 모양을 A, 2x2의 모양을 B라고 하자.

A는 가로를 1만큼 차지하고 B는 한번에 2만큼 차지한다. 따라서 2xn의 모양에서 
n = (1 x A의개수) + (2 x B의개수)라는 수식을 세울 수 있다. A와 B의 범위는 0과 자연수이다. 따라서 A와 B의 순서쌍 조합을 구하면 이 과정에서 조합을 이용한 공식을 세울 수 있다.

- n이 홀수이면 n = 2*k +1
2xn 타일링 경우의 수 = (k+1)C1 + (k+2)C3 + (k+3)C5 + ... + (2k+1)C(2k+1)
- n이 짝수이면 n = 2*k
2xn 타일링 경우의 수 = kC0 + (k+1)C2+ (k+2)C4 + ... + (2k)C(2k)

근데 이거 계산이 ... 시간초과가 안될리 없었다. 큰 문제를 작은 문제로 쪼개서 해결할 수 있다는 점에서 이 문제는 DP를 이용해야 했다.
그래서 차근차근 경우의 수를 생각해보았더니 dp[n] = dp[n-2] + dp[n-1] 이라는 점화식을 구할 수 있었다.

dp[n]은 2xn타일링 경우의 수를 의미한다. 2xn의 타일링 조합은 2x(n-2)의 타일에 B를 붙이는 경우, 2x(n-1)의 타일에 A를 붙이는 경우로 나눌 수 있다. 따라서 dp[n] = dp[n-2] + dp[n-1]의 점화식이 성립하는 것이다.

 

📍코드:

#include <iostream>
using namespace std;

int main(){
    int n; cin>>n;
    int dp[n+1];
    if(n==1||n==2){
        cout<<n<<endl;
    }else{
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<n+1;i++){
            dp[i] = (dp[i-2] + dp[i-1])%10007;
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}