Problem Solving/BOJ

[백준 11727번] [동적 계획법] 2xn 타일링 2

  • -
728x90
반응형

Approach

문제를 잘 보면 전체적으로 이전의 결과가 이후의 결과에 계속 영향을 주는 것을 알 수 있고

해당하는 경향성을 점화식을 통해 일반화해서 나타낼 수 있음을 쉽게 파악할 수 있다.

 

이 지점에서 DP문제를 떠올려 주면 된다.

 

다만, 이 문제에서 어느 블록을 이전에 썼는지를 파악해야 경우의 수를 더할 수 있으므로

각 타일의 종류마다 따로 DP를 할당해서 점화식을 세워주면 된다.

 

에를 들어

dp[i][1], dp[i][2], dp[i][3]을 각각 i번째 가로에 1 x 2, 2 x 1, 2 x 2 블럭을 사용했을 때의 경우의 수라고 하면 점화식을 다음과 같이 나타낼 수 있다.

$$ dp[i][1] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]$$

$$dp[i][2] = dp[i - 2][1] + dp[i - 2][2] + dp[i - 2][3]$$

$$dp[i][3] = dp[i - 2][1] + dp[i - 2][2] + dp[i - 2][3]$$

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int dp[1001][3];

int main(void){
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;
    dp[2][1] = 1;
    dp[2][2] = 1;
    dp[2][3] = 1;

    int n;
    cin >> n;

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

    int result = (dp[n][1] + dp[n][2] + dp[n][3]) % 10007;
    cout << result << "\n";

    return 0;
}
반응형
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.