[백준BOJ] 11726번 2×n 타일링.py

 

 

백준 저지에서 2xn 타일링을 파이썬을 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

11726번 2×n 타일링.py

tomy9729/Algorithm

 

 

1259번 팰린드롬수

문제

2 ×n 크기의 직사각형을 1 × 2, 2 ×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2 × 5 크기의 직사각형을 채운 한 가지 방법의 예이다.

설명

n의 크기별로 규칙성을 찾아야 한다. 만약 모르겠다면 n=1부터 하나씩 해보는 것도 좋은 방법이다. n=1부터 5 정도까지 해보면 다음 점화식을 찾을 수 있다.

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

재귀 함수로도 풀 수 있겠지만 반복문을 통해 모든 n에 대한 값을 구하는 것도 오래 걸리지 않을 것 같아서 전부 구한 다음 원하는 값을 출력하도록 했다. 지금 생각해보니 입력받은 n까지만 구하는 게 더 좋았을 것 같다.

코드

#11726번 2×n 타일링
if __name__ == "__main__":
  n = int(input())
  tile = [0]*1001
  tile[1] = 1
  tile[2] = 2
  for i in range(3,1001) : 
    tile[i] = (tile[i-1] + tile[i-2])%10007
  print(tile[n])