[BOJ] [Python] 11726번 : 2xn 타일링

 

규칙 찾기

 

 

타일링해야 하는 직사각형은 2 x N으로 고정이기 때문에,  1 x 2 직사각형 2개를 1개로 보고 풀었다.

2 x 1 타일로만 이루어지는 경우는 나중에 + 1 을 해주는 방식으로 처리했다.

 

 

찾은 규칙

N의 짝 홀수 상관없이 앞에 방법(순서를 바꿨을 때 1 x 2 과 2 x 1의 개수가 같으면, 같은 방법이라 생각한다.)에 2 x 1 타일을 1개 붙여서 가져간 다음, 순서를 고려한 것이 총 경우의 수[답에서 요구하는 방법의 수]가 된다. 거기에 짝수일 경우에는 1 x 2 직사각형을 이용한 방법 1개를 추가한다.

 

 

코드로 나타내기

한 방법에 1 x 2 와 2 x 1이 몇 개가 쓰였는지 개수만 센다.

그리고 다음 순서에 그 전 순서의 방법들에 사용됐던  2 x 1 타일 수에 1을 더해주는 것이다. 

짝수일 경우에는 1 x 2 타일 수에 N / 2 수를 추가한다.

 

마지막으로 개수만 셌기 때문에, '같은 것이 있는 순열' 공식을 사용해서 방법의 수를 계산한다.

 

 

결과를 보며, 마무리 하겠다.

 

결과 출력

 

전자 리스트는 2 x 1의 타일 개수를 가지고 있고,  

후자 리스트는 1 x 2의 타일 개수를 가지고 있다.

 

동일 인덱스는 1개의 방법 내에 쓰인 2 x 1과 1 x 2의 개수이다.

예를 들어, 인덱스 0번은 2개의 방법 중 1개이고 2  x 1이 3개, 1 x 2가 1개가 쓰인 것이다.

이 방법의 경우의 수는 4! / 3! * 1! 이다. 

 

방법마다 경우의 수를 계산하여, 모두 더하면 정답이 된다. (마지막에 +1을 하는 것까지 포함)

 

 

 

* 같은 것이 있는 순열 : 만약 aaabb를 나열하는 경우의 수를 예로 들면, 5! / 3! * 2! 이다. 

 

 

def factorial(num):

    result = 1

    for n in range(1, num + 1):
        result *= n

    return result


def cal(num):
    one = [0]
    two = [1]

    for i in range(3, num + 1):

        for j in range(len(one)):
            one[j] += 1

        if not i % 2:  # 짝수
            one.append(0)
            two.append(i // 2)

    # print(one, two)
    result = 0

    for x in range(len(one)):
        result += (factorial(one[x] + two[x])) // (factorial(one[x]) * factorial(two[x]))

    return result + 1


i_num = int(input())

if i_num == 1:
    print(1)

else:
    print(cal(i_num) % 10007)

 

 

 

내가 찾은 규칙보다 더 간단한 규칙이 있었다.

 

2 x 1, 2 x 2, 2 x 3, 2 x 4 ... 의 개수를 세보면, 1, 2, 3, 5, 8 ... 이런 식으로 피보나치 수열이 나온다.

f(n) = f(n - 1) + f(n - 2)

 

단,

n = 1, f(n) = 1

n = 2, f(n) = 2