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

문제 링크

성공 여부(걸린 시간): 성공 (20분)

아이디어

우선 타일의 조합에 대해서 보면

조합으로 이루어졌을 때 최소의 단위가 되는 그러한 조합은 너비가 1, 2인 2가지이다.

각 너비가 1, 2인 블럭의 조합을 구해보면

1. 너비가 1인 블럭의 조합은 아래의 하나이다.

2. 너비가 2인 블럭의 조합은 아래와 같이 2가지이다.

빨간 색으로 곱표를 표시한 조합도 너비가 2인 블럭 조합아닌가요?

-> 너비가 2인 조합은 맞죠. 그러나 너비가 1인 조합이 2개가 합쳐진 조합이고

최소단위가 아니기 때문에 제외했습니다.

 

최소단위가 아니라서 제외한다는 말은 저 블럭들 | | 중에 오른쪽 | 블럭 하나가 없다면

결국 dp[i - 1]에서도 반영이 되는 값이기 때문에

이 블럭의 조합이 더 작은 너비로 나눠질 수 없어야 한다는 말과 대동소이합니다.

 

그래서 이 조합들을 통해 알 수 있는 것은

만약 i가 3이상의 값일때

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

 

라는 식이 나오게 됩니다. 

 

풀어서 설명하면 

 

dp [i - 1]은 1칸 전에서 지금의 i의 칸으로 도달할 수 있는 경우의 수인데 

1칸에 대한 조합은 1가지 뿐이므로 dp[i - 1] * 1과 같습니다.

 

또한 dp[i - 2]는 2칸 전에서 지금의  i의 칸으로 도달할 수 있는 경우의 수로

2칸 블럭에 대한 최소단위에 대한 조합은 2가지이므로 2칸 전에 도달할 수 있었던 경우의 수에 2배를 한

dp[i - 2] * 2와 같습니다. 이를 더해주면서 i값을 최신화 해주면 끝입니다.

 

풀이 코드

#include<iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int dp[1001] = {0,};
    int N;
    cin >> N;
    dp[1] = 1;
    dp[2] = 3;
    for (int i = 3; i <= N; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
    }
    cout << dp[N];
    return 0;
}