[백준] 11727번 (python 파이썬)

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

11727번: 2×n 타일링 2

 

 

width = int(input())

if width == 1:
  print(1)
elif width == 2:
  print(3)
else:
  cache = [0] * (width + 1)
  cache[1] = 1
  cache[2] = 3
  for i in range(3, width+1):
    cache[i] = cache[i-1] + cache[i-2] * 2
  print(cache[width] % 10007)

 

• 부분 반복 구조 : cache[ i ] = cache[ i - 1 ] + cache[ i - 2 ] * 2
• 최적 부분 구조 : cache[ i ]은 cache[ i - 1 ]와 cache[ i - 2 ]의 최적의 해로 구할 수 있다. 하지만, 애초에 cache[ n ]의 값은 1개만 나오기 때문에 그 답이 최적의 해가 될 수 밖에 없다.
• 메모이제이션 :  각 길이별로 캐쉬를 만든다. cache = [0] * (width + 1)
• 접근 방식 : bottom - up 방식 ( 이유 : cache[1]과 cache[2]를 알고있으므로 생각하기 쉽다.)

아래의 코드는 top - bottom 방식의 코드이다.

width = int(input())

cache = [0] * (width + 1)
def get_cache(width):
  if cache[width]:
    return cache[width]
  elif width == 1:
    cache[1] = 1
  elif width == 2:
    cache[2] = 3
  else:
    cache[width] = get_cache(width - 1) + get_cache(width - 2) * 2
  return cache[width]

print(get_cache(width) % 10007)

하지만 이 코드는 재귀스택을 너무 많이 쌓아서 에러가 난다. 참고로 파이썬의 기본 최대 재귀 깊이는 1000이다.

 

import sys
sys.setrecursionlimit(10**6)

이 코드를 넣어주면 재귀 깊이를 설정해 줄 수 있다. 깊이를 백만으로 하니까 잘 동작한다.

하지만 백준과 같은 코딩 테스트에서 사용할 순 없다.

따라서 이 문제는 bottom - up 방식으로만 풀어야 한다.