백준 1720 타일 코드

1720번: 타일 코드

문제

2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다.

그런데 문제가 생겼다. 넓은 판을 교환하다 보니 좌우 대칭인 경우가 있어, 뒤집히는 경우 코드가 헷갈리게 되는 경우가 발생한 것이다. 예를 들어 아래의 두 경우는 달라 보이지만 좌우 대칭을 이루고 있다.

N이 주어지면, 전체 타일 코드의 개수를 구하는 프로그램을 작성하시오. (단, 서로 좌우 대칭을 이루는 중복된 표현은 한 가지 경우로만 처리한다.)

 

dp문제이다. 예전에 풀었던  2xn 타일링2 문제를 응용해서 풀었다.

모든 경우의 수에서 서로 좌우 대칭을 이루는 경우를 빼주면 된다. 

다시 보면서 느낀건데 dp2 해줄 필요 없이 그냥 (dp[n]-dp1[n])/2 + dp1[n] 해줘도 될 듯하다.

dp : 모든 2x1 1x2 타일의 경우

점화식 dp[i] = dp[i-1]+2*dp[i-2]

dp1 : 완전 대칭일 경우 

점화식 dp1[i] = dp1[i-2]+2*dp1[i-4]

dp2 : 답

 

 

#include <iostream>
 
using namespace std;
 
int main(void)
{
    int n;
    cin >> n;
 
    long long int dp[31];
    long long int dp1[31];    // 완전 대칭
    long long int dp2[31];
 
    dp1[0] = 0;
    dp1[1] = 1;
    dp1[2] = 3;
    dp1[3] = 1;
    dp1[4] = 5;
 
    for (int i = 5; i <= n; ++i) {
        dp1[i] = dp1[i - 2] + 2 * dp1[i - 4];
    }
    
 
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 3;
    dp[3] = 5;
 
    for (int i = 4; i <= n; ++i) {
        dp[i] = dp[i - 1] + 2 * dp[i - 2];
    }
 
    dp2[0] = 0;
    for (int i = 1; i <= 31; ++i) {
        dp2[i] = (dp[i] - dp1[i]) / 2 + dp1[i];
    }
    cout << dp2[n] << endl;
    
    return 0;
}