백준 1720 자두나무

문제

전형적인 2xN 타일링 문제지만 좌우대칭이 되는 경우는 1번으로 카운팅하자.

풀이

완벽한 좌우대칭인 경우를 생각하면 쉽게 풀린다.

N이 짝수인 경우에는 중간에 아무 것도 없거나 두 칸짜리 타일이 올 수 있다.

N이 홀수인 경우에는 중간에 한 칸짜리 타일만 올 수 있다.

따라서 길이 N의 타일링 경우가 모두 계산되어 있는 경우라면 계산 가능하다.

코드

#include <iostream>
#include <cstring>
using namespace std;

int N;
int cache[31];

int solve(int n) {
    if(n<=0)
        return 0;
    int &ret = cache[n];
    if(ret!=-1)
        return ret;
    if(n==1 || n==2) {
        ret = n;
    }
    else
        ret = 0;
    ret += solve(n-1) + solve(n-2) * 2;
    return ret;
}
int main() {
    cin>>N;
    memset(cache, -1, sizeof(cache));
    solve(N);
    cache[0] = 1;
    
    int ret = 0;
    if(N%2==0)
        ret = (cache[N] - cache[N/2] - cache[N/2-1]*2)/2 + cache[N/2] + cache[N/2-1]*2;
    else
        ret = (cache[N] - cache[N/2]) / 2 + cache[N/2];
    cout<<ret;
    //std::cout << "Hello, World!" << std::endl;
    return 0;
}

Written by@[jungin]

안녕하세요

GitHub