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

🏆 목차.

1. 문제
2. 코드
3. 풀이

 

🛒 문제

 

백준 11726번 2xn 타일링

 

🎨 코드

 

#include<iostream>
#include<vector>
using namespace std;

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

 

🎯 풀이

 

해당 문제는 다이내믹 프로그래밍(DP)을 통해 간단히 해결가능한 문제이다.

말로 설명하면 이해하기 어렵기 때문에 그림으로 설명하겠습니다.

 

2xn 타일링 규칙

 

위 그림을 통해 2xn은 규칙을 가지고 있는 것을 알 수 있습니다.

2x3 = 2x2 + 2x1

2x4 = 2x3 + 2x2

 

이런식으로 dp [n] = dp [n-1] + dp [n-2]라는 규칙이 있는 것을 알 수 있고 이를 통해 간단하게 문제를 해결할 수 있습니다.

 

2x1은 타일 하나만 들어가니 1로 초기화를 하고,

2x2는 두개의 경우의 수가 있으니 2로 초기화했습니다.

 

그리고 이후에는 반복문을 통해 규칙을 코드로 구현했고,

문제에서 10007로 나눈 나머지를 출력한다고 했기 때문에 dp [i]%= 10007을 해주었습니다.