1720번

1720번 - 타일 코드

http://m.blog.daum.net/rhaoslikesan/369?tp_nil_a=2

위의 블로그에서 풀이 과정을 참고하였다. 도통 설명된 풀이를 찾을 수가 없었는데 감사합니다.

일단 이 문제는 타일 채우기 문제랑 똑같은데 대칭을 없애야 했다.

그 과정을 참고했는데, 참.. 어떻게 저런 생각을 할 수 있을까 하는 생각이 들었다.

풀이 과정 ↓↓↓

우선 원래 타일을 그냥 채우던 방식대로 재귀함수를 만들었다.

그렇다면 D[N]= D[N-1] + 2*D[N-2]

D 배열 에는 대칭이 중복되서 들어간 모든 타일채우는 방법의 수가 들어있다.

근데 우리는 중복을 하나로 취급해야 한다.

즉 " 전체 타일 개수 = 중복1 + 중복 2 + 중복아닌 것들 " 로 구성이 되는 것을 알 수가 있다. 

(여기서 중복 1, 중복 2는 하나로 줄여야 하는 대칭이 되는 타일 모양이다)

따라서 , 여기서 중복 1, 2를 하나로 만들어야 한다.

처음에 이 중복되는 타일의 수를 찾아서 빼려고 했으나, 이는 엄청나게 어렵고 복잡하고 결국 못해냈다.

그래서 다른 사람들은 바로 '중복 아닌 것들' 을 찾으려고 했다. 중복아닌 것들을 찾아봐야 무슨 소용이 있나 싶었지만 ,

'전체 타일 개수 + 중복 아닌 것들' = '중복1 + 중복 2 + 중복아닌 것들 + 중복아닌 것들 ' 이 된다.

그래서 이 식을 2로 나누면

(전체타일 개수 + 중복아닌 것들) / 2 = (중복 1+ 중복 2 + 중복 아닌 것들 + 중복 아닌 것들 ) 이 되고

                                                = (중복 + 중복 아닌 것들)

이 되서 결국 찾고자 하는 중복이 제거된 타일을 붙이는 방법의 갯수가 된다...

그래서 중복 아닌 것들을 찾는 방법은 맨 중앙 지점으로부터 양쪽이 완전 대칭이 되도록 타일이 깔리면 된다. 그러면 완전 좌우대칭이 되므로

중복되는 값이 아닌 1개의 값으로 들어가게 된다.

그래서 이를 짝수일 때와, 홀수인 경우로 나눠야 했다.

짝수인 경우에는 D[N/2] + D[N/2 - 1] 인 갯수(그냥 대칭이거나, 가운데 2*2 타일을 만드는 방법이 있는 대칭)

홀수인 경우에는 가운데 l 하나가 있고 대칭인 경우이므로 D[N/2] 의 갯수.

<정답 코드>

#include<iostream>
#include<string.h>
 
using namespace std;
int D[31];
int go(int n)
{
    if (n < 0)
    {
        return 0;
    }
    if (n == 0)
    {
        return 1;
    }
    if (D[n] >= 0)
    {
        return D[n];
    }
    if (D[n] == -1)
    {
        D[n] = 0;
    }
 
    D[n] = go(n - 1) + 2 * go(n - 2);
 
    return D[n];
    
}
int main()
{
    int N;
    memset(D, -1, sizeof(D));
    cin >> N;
    
    go(N);
    int ans = 0;
    if (N % 2 == 0)
    {
        ans = (go(N) + (go(N / 2) + 2 * go(N / 2 - 1)))/2;
        cout << ans << endl;
    }
    else
    {
        ans = (go(N) +  go(N / 2))/2;
        cout << ans << endl;
    }
    return 0;
}