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

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

11726번: 2×n 타일링

 

width = int(input())

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

 

 

• 부분 반복 구조 : cache[n] = cache[n-1] + cache[n-2]
• 최적 부분 구조 : n에 따라 최적의 값이 도출되는 것이 아니라 값 자체가 하나밖에 없다.
• 메모이제이션 : n+1 크기의 배열 cache 생성
• 접근 방식 : bottom - up 방식 ( 이유 : cache[1]과 cache[2]를 알고있으므로 생각하기 쉽다.)

아래는 top - down 방식으로 짠 코드이다.

width = int(input())

cache = [0] * (width + 1)

def get_cache(i):
  if cache[i]:  
    return cache[i]
  if 1 <= i <= 2:
    cache[i] = i
  else:
    cache[i] = get_cache(i-2) + get_cache(i-1)
  return cache[i]
  
print(get_cache(width) % 10007)