[백준] 1720번: 타일 코드

1720번: 타일 코드

문제

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

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

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

입력

첫째 줄에 타일의 크기 N(1≤N≤30)이 주어진다.

출력

첫째 줄에 타일 코드의 개수를 출력한다.

예제 입력 1

4

예제 출력 1

8

 

예제에서와 같이 서로 뒤집었을 때 모양이 같은 경우는 1개의 케이스로 생각해주는 문제입니다. 뒤집었을 때 모양이 같은 케이스가 없는 경우가 있습니다. 완전히 좌우가 대칭인 경우가 그렇습니다. 중복된 케이스를 제거하는 것은 어렵지만, 좌우가 대칭인 케이스를 찾는 것은 그렇게 어렵지 않습니다. 좌우가 대칭인 케이스의 경우의 수를 찾고, 그걸 더한 다음 2로 나눠주면, 중복된 케이스를 제거할 수 있습니다. 

 

#include <iostream>
using namespace std;

long long dp[31];

int main() {
    int n;
    cin >> n;
    
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] * 2;
    }
    
    long long ans = 0;
    if (n % 2 == 1) {
        ans = (dp[n] + dp[(n - 1) / 2]) / 2;
    } else {
        ans = (dp[n] + dp[n / 2] + dp[(n - 2) / 2] * 2) / 2;
    }
    
    cout << ans << '\n';
    
    return 0;
}