[백준-11726] 2*n 타일링 - 동적계획법 이용하기

# 문제

 

#풀이

첫 시도는 늘어나는 n에대해서 1또는 2의 합으로만 구성되면 된다고 생각했음. 

 즉 n=5일 경우 1+1+1+1+1이 되고, 1과 2의 합으로 5를 만드는 모든 경우의 수를 구하면 된다고 생각했다. 확통시간에 배운 경우의 수를 활용하면 풀 수 있을것 같았지만 기억이 나지 않았다.

 n이 늘어나는 경우 결국 앞선것을 재활용하면 되기 때문에 점화 관계를 찾아서 문제를 풀었다.

 

# 코드

def answer(n):
  if (n <= 1) :
    return 1
  list = [0 for i in range(n + 1)]
  list[1] = 1
  list[2] = 2
  for i in range(3, n + 1):
    list[i] = list[i - 1] + list[i - 2]
  return list[n] % 10_007


if __name__ == '__main__':
  solve = answer(int(input()))
  print(solve)