[동적프로그래밍]백준 11726,11727번 2 x n 타일링 1,2) (C++)

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

 

해당 문제는 2 x N 타일안에 직사각형을 1 x 2 와 2 x 1로 채우는 경우의 수를 구하는 것이다.

 

 

예를들어 2 x 1의 경우 세로로 세워진 직사각형 하나만 들어가므로 1

2 x 2의 경우 둘다 누워있거나 둘다 서있는 직사각형만 들어가므로 2

이렇게 되는 것이다.

 

그렇다면, 이걸 어떻게 구해야 할까?

 

먼저 n번째 타일의 갯수를 구할 때, 맨 마지막에 채우는 타일이 저렇게 있다면 n-1의 값과 n의 값은 같은 것일것은 이해가 갈 것이다.

 

그렇다고 만약 모든 값이 같아지게 되면 당연히 답은 아닐것이다. 이때 생각해야 하는게 또 다른 경우의 수이다.

바로 이것이다. 이렇게 마지막에 채워지는 값에 대한 경우의수는 이것 2가지 밖에 없다.

 

2 x 2와 2 x 1인 것이다.

 

그렇다면 n의 값 = n-1의 값 + n-2의 값이므로

 

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

int main()

{

    int n;

    cin >> n;

    int dp[n + 1];

    dp[1] = 1;

    // 2*1의 경우 1개

    dp[2] = 2;

    // 2*2 의 경우 2개

    for (int i = 3; i < n + 1; i++)

    {

        dp[i] = dp[i - 1] + dp[i - 2];

        dp[i] %= 10007; // 모듈러

    }

    cout << dp[n];

}

이런 식이 나오게 된다.

 

이걸 풀었다면 11727번을 매우 쉽게 풀 수 있을 것이다.

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

해당 문제는 앞선 경우의 수에서 단순히 2 x 2로도 채울 수 있는 경우가 생긴 것이다.

 

그렇다고해서 문제를 푸는 방식에 달라지는 것은 없다

 

이 경우의 수만 또 더해주면 된다 

그렇게 되면

 

n-1 + n-2 + n-2가 되며

 

식으로 표현 시

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

    int n;

    cin >> n;

    int dp[n];

    dp[1] = 1;

    dp[2] = 3;

    for (int i = 3; i < n + 1; i++)

    {

        dp[i] = dp[i - 1] + dp[i - 2] * 2;

        dp[i] %= 10007;

    }

    cout << dp[n];

}

 

이렇게 나온다.

 

dp의 기본적인 특징을 반드시 알아라 작은 해답으로써 큰 해답을 얻는것이 핵심이며,

처음 경우의 수는 단순하게라도 알아보는 것이 중요할 것이다.