반응형
타일 싫어...
진짜 엄청 고민했던 문제.
겹치는 경우가 많아서 겹치지 않는 경우로 세야한다.
n=3인 경우,
여기서 잘보면 두가지로 분류 할 수 있는데,
처음에 2*1이 온 경우와, 처음에 2*2또는 1*2가 온 경우이다.
처음에 2*1이 온 경우, n=3이므로 1을 뺀, n(2)와 같은 값을 가진다.
처음에 2*2나 1*2가 온 경우, n=3이므로, 2만큼 뺀, n(1)만큼의 값을 가진다.
따라서 일반항은 n(k)=n(k-1)+2*n(k-1)이다.
다시한번 살펴보면, 빨간 박스(2*2)는 처음 세는 값이므로 여기에는 이전 값의 모든 값이 와도 된다.
하지만 두번째, 파란박스에는 ㅣㅣ(2*1 2개)가 오면 빨간 박스와 겹치는 경우가 생긴다.
그래서 파란 박스에 올 수 있는 경우 중 2*2와 1*2 두개만 카운트 해서 2를 곱해주는 것이다.
dp=[0 for x in range(251)]
dp[0]=1
dp[1]=1
for x in range(2,251):
dp[x]=dp[x-1]+2*dp[x-2]
while (1):
try:
n=int(input())
print(dp[n])
except:
break반응형
