[코드트리 챌린지] 3주차 DP l - subproblem을 그대로 합치면 되는 DP / 사각형 채우기

 

https://www.codetree.ai/missions/2/problems/rectangle-fill/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[1005];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    dp[1] = 1;
    dp[2] = 2;

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

    cout << dp[n];
}

 

위 사진으로 잘 설명될 수 있을지 모르겠습니다.

dp[1] , dp[2]를 초기 조건으로 설정하여 dp 배열에 저장하도록 합니다.

문제는 dp[3]을 저장하는 부분부터 입니다. dp[3] 부터는 단순 눈대중으로 구하기엔 어려움이 있습니다.

이것을 해결하기 위한 방법이 바로 위의 사진입니다.
2 x 3 블록의 오른쪽 부분을 2 x 1 과 2 x 2로 채운 후 나머지 부분을 채우는 경우의 수를 구하는 방법입니다.

근데 이떄 사진을 잘 보면 2 x 1 블럭으로 오른쪽을 채웠을 때 남는 부분인 2 x 2 블럭을 채우는 경우는
우리가 이미 dp[2]에서 구해놨기에 이를 가져오면 알 수 있고 2 x 2로 채우는 경우는 남는 부분이 2 x 1이여서
이 또한 dp[1]에서 구해놨기에 알 수 있습니다.

즉 이를 일반화 해보면 오른쪽 구석을 2 x 1 로 채운 경우 -> 나머지 2 x n-1 를 채우는 경우를 구하면 되고
오른쪽 구석을 2 x 1 로 채운 경우 -> 나머지 2 x n-2를 채우는 경우를 구하여 그 둘을 더하면 2 x n을
채우는 방법의 수를 구할 수 있습니다.

즉 dp[n] = dp[n-1] + dp[n-2] 입니다.