백준 11726번 (2xn 타일링) c++

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

11726번: 2×n 타일링

문제 풀이

 

이 문제는 DP를 이용하여 푸는 문제이다.

다른 많은 풀이 사이트에서는 단순히 DP[i] = DP[i-1] + DP[i-2] 라는 이유를 N에 따라 세어보았을 때 이게 말이 된다라는 식으로 많이 적어놓았다.

하지만 밑에 적어 놓은 것을 보면 제대로 된 규칙을 알 수 있다.

DP[i-2] 에는 1x2인 2개의 타일이 붙고,
DP[i-1] 에는 2x1인 1개의 타일이 붙은 두가지 경우의 수를 합치면 DP[i]가 완성되는 것이다.

 

전체 코드

#include <iostream>

using namespace std;

int dp[1001] = {0,};

int main(){

        int N;

        cin >> N;

        dp[0] = 1;
        dp[1] = 1;

        for(register int i = 2; i <= N; i++){
                dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }

        cout << dp[N] << '\n';

        return 0;

}