BOJ 1720번 타일 코드

BOJ : https://www.acmicpc.net/problem/1720

github : https://github.com/junho0956/Algorithm/blob/master/1720/1720/%EC%86%8C%EC%8A%A4.cpp

 

타일맞추는거 정말어렵습니다. 진짜 너무 어렵네요

 

타일을 맞출 수 있는 모든 가지의 수는 쉽게 구할 수 있습니다.

문제의 조건은 중복되는 수는 2가 아닌 1로 즉, 중복되는 수를 감소시켜야 되는 문제입니다.

 

대체 어떻게 중복되는 수를 찾아야되는지 고민했습니다.

 

식을 이렇게 세워봤습니다.

중복되는 수를 A, 중복되지 않는 수를 B라고 했을 때

원하는 답 : 2A + B - A = A+B

즉 2A+B 에서 A+B 를 만들어야하는 문제였습니다. -A 를 어떻게 찾아야되는지 계속 고민했습니다.

결국 실패했고,, 다른 방법을 찾은게 B 즉, 중복되지 않는 수를 찾아보는 것이였습니다.

2A+B+B / 2 = A+B 이니 원하는 답은 같으니까요

 

중복되지 않는 수는 의외로 쉽게 구할 수 있었습니다.

중복되지 않는 수는 즉 순대칭? 같은 배열을 뜻합니다. 그렸을 때 딱 1번만 보여지는 배열 즉, 

예를 들면 가로*세로 기준 2*1 로만 쭉 채운 모양을 말합니다.

이때 중복되지 않는 수는 N이 짝수일때와 홀수일때로 나눌 수 있습니다.

 

가장 먼저 제 코드에서 아셔야 하는 것은 dp의 값 상태입니다.

저는 재귀로 dp를 해결하는 것을 좋아해서 다른분들과는 반대로 dp[0]이 최종값을 의미하게 됩니다.

dp[0] = 재귀... = 재귀... 이런 형태를 띄게되니까요

 

N이 홀수일 경우를 먼저 고려해보면, 

만약 N이 5이면 순대칭? 을 만들기 위해서는 2부분에 2*1 타일을 넣고 나머지 0~1 부분에 아무거나 넣는것입니다.

즉 N이 홀수일 경우 순대칭배열은 dp[N/2-1] 경우의수입니다.

즉 제 코드 기준으로는 dp[0]이 dp[N]이 되니 순서가 바뀐다는 것을 생각해서

(dp[0]+dp[N/2+1]) / 2 가 N이 홀수일 경우 (2A+B+B)/2 = answer를 만드는 공식이 됩니다.

 

N이 짝수일 경우를 고려해보면,

만약 N이 6이면 순대칭? 을 만들기 위해서는 2가지 경우가 존재하게 됩니다.

1) N/2를 정확히 나눠서 N/2-1, N/2+1에는 2*1 타일을 넣는 경우

2) (N/2-1)~(N/2+1) 에 1*2 | 2*2 타일을 넣는 경우가 됩니다.

 

dp[n] 을 길이 n까지 타일을 넣을 수 있는 모든 경우의 수라고 가정하면,

dp[n] = dp[n-1]+dp[n-2] (즉, 길이가 1 적을때와 2 적을때의 모든 경우) 가 된다는 것을 안다면

 

N이 짝수일 경우 순대칭배열은 dp[N/2]+dp[N/2-1] = dp[N/2+1] 이 되게 되고

제 코드 기준상 반대로 뒤집으면 dp[N/2-1] 이 되게 됩니다.

(dp[0]+dp[N/2-1]) / 2 가 N이 짝수일 경우 (2A+B+B)/2 = answer를 만드는 공식이 됩니다.

 

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
 
ll dp[31];
int N;
 
ll solve(int x) {
    if (x > N) return 0;
    if (x == N) return 1;
 
    ll& res = dp[x];
    if (res) return res;
 
    res = solve(x + 1) + solve(x + 2)*2;
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
 
    ll ans = solve(0);
    if (N % 2) {
        ans = (dp[0] + dp[N / 2 + 1]) / 2;
        if (N == 1) ans = 1;
    }
    else {
        ans = (dp[0] + dp[N / 2 - 1]) / 2;
    }
 
    cout << ans;
    return 0;
}