https://algospot.com/judge/problem/read/ASYMTILING

안녕하세요.

ASYMTILING 문제를 풀다가 궁금한 사항이 있어서 이렇게 문의를 남깁니다.

1. 문의사항:

기존의 피보나치 수열을 이용해서 푸는 방법 말고 다른 방법으로 풀려고

하는데 문제 속에서 n의 값이 커지면 (n > 81 일 때) 값이 조금씩 달라집니다.

1. 사용한 방법

일단 n 이 주어졌을 때, Tile을 채울 수 있는 총 경우의 수를 다음과 같이

추론했습니다.

n = 2*x + y, where x = 가로 막대 쌍의 갯수, y = 세로 막대의 갯수

예를 들어, 2x5의 공간을 채울 때, 1X5의 공간만 고려를 합니다.

가로막대는 1x2, 세로막대는 1x1로 계산을 합니다.

그렇다면 가능한 조합의 경우는 다음과 같습니다.

n = 5

가로막대의 갯수 세로막대의 갯수 가능한 조합의 갯수
0 5 5C0 = 1
1 3 4C1 = 4
2 1 3C1 = 3

총 8개의 조합이 가능합니다.

이 중에서 대칭인 조합을 빼주는 것으로 계산했습니다.

대칭인 조합은 n이 짝수, 홀수인 경우로 구분해서 계산했습니다.

n = 2*x + y 일 때, where x = 가로막대 쌍의 갯수, y = 세로 막대의 갯수

n = 홀수
가로막대 쌍의 갯수(x)가 짝수일 때만 대칭인 조합이 가능

세로 막대 하나를 정 가운데 놓고 나머지 막대들을 종류별로 반절로 나누어

n / 2 의 공간에 배치를 합니다.

그렇게 하면 주어진 x, y의 경우에는 ((x-1)/2 + y/2)C(y/2) 개의 대칭인 조합이

존재 할 수 있습니다.

n이 가지고 있는 모든 x, y의 경우에 대한 대칭조합의 합을 구합니다.

n = 짝수
x = 홀수
가로막대(x)를 하나 가운데 놓고 남은 막대들을 종류별로 절반으로 나누어
(n/2) -1 의 공간에 배치를 합니다.

이런 경우의 수는 ((x-1)/2 + y/2)C(y/2)

x = 짝수
막대들을 종류별로 절반으로 나누어서 n/2 의 공간에 배치합니다.

이런 경우의 수는 (x/2 + y/2)C(y/2)

이런 방식으로 구현을 한 코드는 다음과 같습니다.

import math
import numpy as np

def find(n):
all_combo = 0
case = 0

f = math.factorial

if n % 2 == 0:
    case = n/2 + 1  

else:
    case = (n-1)/2 + 1

for x in np.arange(case):
    all_combo += int( f(n - x) / (f(n - 2*x) * f(x)) ) 

total_symmetric = 0

if n % 2 == 0:
    for x in np.arange(case):

        if (x) % 2 == 0:
            total_symmetric += int( f(int(x/2) + int((n - 2*x)/2)) / (f(int(x/2)) * f(int((n - 2*x)/2))) ) 

        else:
            total_symmetric += int( f(int((x-1)/2) + int((n - 2*(x))/2)) / (f(int((x-1)/2)) * f(int((n - 2*(x))/2))) ) 


else:   

    for x in np.arange(case):

        if (x) % 2 == 0:
            total_symmetric += int( f(  int( (x) / 2 ) + int( (n - 2*x - 1) /2) ) / ( f( int( (x)/2 ) ) * f(int((n - 2*x - 1)/2))) ) 

result = all_combo - total_symmetric

return result

num_case = int(input())

for _ in range(num_case):
n = int(input())
result = find(n)
print(result % 1000000007)

이렇게 구현을 하면 n이 81일 때까지는 값이 정상적으로 나옵니다.

허나 82부터는 값이 아주 조금씩 달라집니다.

저의 생각엔 모든 경우의 수가 고려된 것 같은데

혹시 제가 빠트린 것이 있는지 하여 이렇게 문의를 남깁니다.