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

Silver III

# 11727 2xn 타일링 2

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

11727번: 2×n 타일링 2

 

풀이

n = int(input())
dp = [0] * n
dp[0] = 1

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

print(dp[-1] % 10007)

 

후기

• 이전 문제인 11726과 동일한 유형의 문제다. 수열의 n번째 값을 찾고 규칙성을 발견하는 것이 중요하다.
  2022.02.26 - [Algorithm Study/Python] - [백준 파이썬] # 11726 2xn 타일링
• 조합을 사용하면 i번째 값을 더 빠르게 구할 수 있다. (11726과 같은 방식으로 풀이)
  ex) 2x1은 o, 1x2 또는 2x2는 □로 치환 (□는 각각 2가지 경우를 갖는다)
      n이 5일 때
          ooooo : 5!/5! = 1
          ooo□ : 4!/3!1! * 2 = 8
          o□□ : 3!/1!2! * 2 * 2 = 12
      → 1+8+12 = 21
  
  
• i-1, i값의 차이인 계차를 통해서 규칙을 발견할 수 있었다.
  1) 문제에서 주어진 수열은 [1, 3, 5, 11, 21, 43, 85, 171 ...]과 같이 작성할 수 있다
  2) 계차수열의 리스트는 [2, 2, 6, 10, 22, 42, 86 ...]이다.
  3) 수열과 계차수열을 비교해보았을 때, i가 홀수인 경우 계차는 i+1이고, i가 짝수인 경우 계차는 i-1만큼 변한다. 이를 이용해서 조건문을 작성해주었다.