[Python] 백준 11727번 - 2×n 타일링 2

 

오답

처음에는 dfs 로 풀 수 있다고 생각했다. n개의 블럭을 1, 2, 2 칸의 블록으로 채우는 것과 같다고 생각했고, 결국 n 을 만드는 분해합 문제의 변형이 아닐까하고 추측해서 풀었는데. 시간 내에 풀고 어디가 틀렸는지 알아내지 못했다. 

import math
import sys
sys.setrecursionlimit(10**6)

global n 
global cnt
global blocks

def dfs(input, binary):
  global n
  if input == n:
    global cnt 
    global blocks
    cnt += 1
    blocks += binary
    return 
  elif input+1 < n:
    dfs(input+1, binary)
  elif input+2 < n:
    dfs(input+2, binary+1)

if __name__ == '__main__':
  global blocks
  global cnt
  global n
  cnt = 0
  blocks = 0
  n = int(input())
  dfs(0, 0)
  print(cnt*math.pow(2, blocks)%10007)

---

정답

ans = [0, 1, 3]
for i in range(3, 1001):
  val = 2 * ans[i-2] + ans[i-1]
  ans.append(val)
n = int(input())
print(ans[n]%10007)

각 n 마다 들어갈 수 있는 블록의 수를 계산하는 수식이 있었다. 

미리 배열안에 수식으로 정답을 모두 계산해놓고, 필요한 값만 빼오는 방식

 

---

 

#참조

https://pacific-ocean.tistory.com/194

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