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

 

11727번: 2×n 타일링 2

 

1. 문제 설명

2. 풀이과정

해당 문제는 총 3가지의 타일을 사용하여 배치하는 문제이다.

가로의 길이를 하나씩 늘려가며 타일을 배치할 수 있는 경우를 구하고 다음 경우는 이전 경우와 그전 경우를 활용하여 구할 수 있다.

또한 2x1 타일과 2x2 타일은 서로 교환될 수 있으므로 한 가지의 경우를 구한 뒤 2배를 해주면 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 처음 n이 0일 때와 1일 때는 경우의 수가 1가지이다. 따라서 n의 값에 따른 경우의 수를 저장할 리스트를 생성하고 n이 0일 때와 1일 때의 경우의 수를 저장한다. li = [1, 1]
3. 다음 n이 2일 때부터 n까지 각 경우의 수를 구하는데 for i in range(2, n + 1)
4. 해당 경우의 수는 이전 n의 값일 때 경우의 수에 그전 n의 값일 때 경우의 수에 2배를 더해준 값이 된다. 해당 값을 리스트에 추가해 준다. li.append(li[i - 1] + 2 * li[i - 2])
5. 리스트에서 n번째 경우의 수를 10,007로 나눈 나머지의 값을 출력해 준다. print(li[n] % 10007)

반응형

3. 소스코드

import sys

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

li = [1, 1]
for i in range(2, n + 1):
    li.append(li[i - 1] + 2 * li[i - 2])

print(li[n] % 10007)