[ BOJ / 파이썬 ] 2193. 이친수

일단 문제 파악 위해 쭉 경우의 수를 써내려갔다.

 

1자리

1

2자리

10

3자리

100 101

4자리

1000 1001 1010

5자리

10000 10001 10010 10100 10101

 

일단 보통 초기값은 1개나 2개 잡는다고 가정하며 n항과 n-1항 사이 관계식 도출하려고 생각해보는데. 

오 싹 스쳤다..

사실상 5자리수는 4자리수를 안고 있어서는 안된다. 반면, 3자리수부터 2자리, 1자리수는 모두 안고있다.

왜냐하면 바로 다음자리수를 안는다면 11이 연달아서 나오니까!. 1자리, 2자리에서 점차 늘리는건 보통 조건에 부합한다는걸 보장하므로 신경안쓰고! 바로 이전자리수 뺀 모든 자리수들의 합 + 1 이 되는 셈이다. 

..

엥 근데 왜 풀이를 이렇게 했지.. 직관적으로 풀기는 했는데 정리하려니 ... 어쩌다 풀었는지 모르겠다.. 

ㅋㅋㅋ

n = int(input())
dp = [0] * (n+1)
dp[1] = 1
if n > 1:
  dp[2] = 1
  for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n])

 

분명히 뭔 논리를 갖고 이게 나온건데.... ㅋㅋ

하여간 생각 자체는 탑다운으로 하고,

풀이할 때는 바텀업으로 DP테이블 채웠다.