[백준] 11726번 : 2xn 타일링 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11726번: 2×n 타일링

 

1. 문제 설명

2. 풀이과정

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 직사각형의 가로의 길이를 입력받는다. n = int(sys.stdin.readline())
3. 팩토리얼을 계산하는 함수를 생성한다. 이때 재귀함수로 구현하게 되면 RecursionError가 발생하게 되므로 for 문을 사용하여 구현한다. def Factorial(num)
4. 팩토리얼 결과를 저장할 변수를 생성하고 1로 초기화한다. result = 1
5. 1부터 매개변수로 입력받은 값까지 반복하며 for i in range(1, num + 1)
6. 각 수를 차례대로 이전 결과에 곱하여 새로 저장한다. result *= i
7. 최종 결과를 반환한다. return result
8. 경우의 수를 저장할 변수를 생성하고 초기화한다. answer = 0
9. 2x1 타일의 개수에 따라 1x2 타일의 개수가 정해진다. 2x1 타일의 개수는 최소 직사각형의 가로 길이를 2로 나눈 나머지 값만큼 들어가야 하며, 최대 직사각형 가로 길이만큼 들어갈 수 있고 타일의 개수는 1x2 타일로 인하여 2개씩 늘어나야 한다.
10. 2x1 타일을 기준으로 개수를 늘려가며 가능한 경우의 수를 계산하였다. for i in range((n % 2), n + 1, 2)
11. 2x1 타일의 개수가 정해지면 1x2 타일의 개수는 직사각형 가로의 길이에서 2x1 타일의 개수만큼 빼고, 뺀 결과를 2로 나눈 몫의 2배가 될 것이다. 하지만 1x2 타일은 무조건 아래위로 한 쌍을 이루어 배치되게 되므로 가로의 칸 수만 고려해도 상관없다. j = (n - i) // 2
12. 2x1 타일의 개수와 1x2 타일의 개수가 정해지면 배치할 수 있는 조합의 수를 구하여 결과에 더한다. 조합의 수는 전체 타일의 개수 팩토리얼에 각각 타일의 개수 팩토리얼 결과를 곱하여 나눠주면 된다. answer += Factorial(i + j) // (Factorial(i) * Factorial(j))
13. 경우의 수를 10,007로 나눈 나머지를 출력한다. print(answer % 10007)

반응형

3. 소스코드

import sys

n = int(sys.stdin.readline())

def Factorial(num):
    result = 1
    for i in range(1, num + 1):
        result *= i

    return result

answer = 0
for i in range((n % 2), n + 1, 2):
    j = (n - i) // 2
    answer += Factorial(i + j) // (Factorial(i) * Factorial(j))

print(answer % 10007)