[백준 파이썬] # 11726 2xn 타일링

Silver III

# 11726 2xn 타일링

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

11726번: 2×n 타일링

 

풀이

n = int(input())
if n == 1:
    print(1)

else:
    dp = [0] * n
    dp[0] = 1
    dp[1] = 2
    for i in range(2, n):
        dp[i] = dp[i-1]+dp[i-2]

    print(dp[-1] % 10007)

 

후기

• 결과부터 말하자면 피보나치 수열임을 발견할 수 있다. dp를 이용해서 원하는 값을 찾아가도록 구현했다.

• 조합을 이용하면 계산과정을 빠르게 진행시킬 수 있다. 순열/조합에 대해 익숙해지도록 하자.
  n = 5일 때, 2x1 타일을 o, 1x2 타일을 x로 치환해서 생각해보자
      ooooo : 5!/5! = 1
      ooox : 4!/3! = 4
      oxx : 3!/2! = 3
     → 1+4+3 = 8
  
  
• 수의 규칙성을 발견할 때 피보나치 수열을 염두해보자. 손으로 n번째 값을 잘 구한다 해도 규칙성을 빠르게 찾지 못하면 시간이 매우 오래 걸린다. 빠르게 규칙성을 찾아내는것이 중요.