백준 11726 : 2*n 타일 깔기

이 문제는 다이나믹 프로그래밍 문제이다. 타일이 깔리는 규칙을 살펴보면 쉽게 해결할 수 있다.

 

우리는 날카로운 관찰력으로 규칙을 찾아내야 한다.

n은 길이이고, 위의 그림을 보면 규칙을 찾을 수 있다. 바로 특정 한 쪽이

인 경우와

경우이다.

 

n이 1이 늘어날 때 마다 규칙을 살펴보면,

그 전 타일을 구성하는 경우의 수에 한 쪽에 이것을 붙인 것과

전전 타일을 구성하는 경우의 수에

붙인 경우의 수의 합으로 이루어진 것을 볼 수 있다.

X = int(input())
d = [0]*(X+2) # 인덱스 에러가 나지 않게 2를 더해준다. (2를 더해주지 않으면 1을 입력할 경우 d[2]에서 에러가 남)

d[1] = 1
d[2] = 2

for i in range(3,X+1):
  d[i] = d[i-1] +d[i-2]

print(d[X]%10007)

간단하게 코드로 구현하면 이렇다