[Python] 2193번 이친수

오늘 풀어본 문제는 이친수이다

문제에도 나와있듯이 두가지 조건이있다

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두번 연속으로 나타나지않는다.

그러면 우리는 어떻게 n자리수의 이친수를 구해야할까?

두가지로 나누어서 계산해보면 된다
n-1자리수에서의 1로 끝나는 수 와 0으로 끝나는 수의 개수를 알아야한다.

이 이유는 1로 끝나면 조건 2에 의해 또 1이 나오지 못함으로 무조건 0이 붙는다
0으로 끝나게 되면 1과 0 둘다 뒤에 올수있다!

memo = {1:[1,0,1], 2:[1,1,0]}   #1,2자리수의 이친수

def lee(n):   #이전에 계산한 적이 있다면 바로 결과 리턴
  if n in memo:
    return memo[n]

  tmp = lee(n-1)
  memo[n] = [0,0,0]


  memo[n][0] = tmp[1] *2 + tmp[2]   
  #결과값은 마지막수가 0일때 *2 + 마지막수가 1일때 / 0일때는 1과 0이 둘다올수있기 때문에 *2
  memo[n][1] = tmp[1] + tmp[2]
  #마지막숫자가 0일때의 경우는 0으로 끝난수와 1로끝난수의 더하기
  memo[n][2] = tmp[1]
  #마지막숫자가 1일떄의 경우는 0으로 끝난 수 밖에 없다

  return memo[n]
print(lee(int(input()))[0])   #결과 출력

각 리스트값의 의미는 n자리수의 이친수개수,0으로끝난 이친수, 1로끝난 이친수를 뜻한다!

마치며...

동적프로그래밍을 처음엔 이해하기 어려웠지만 지금이제 문제푸는게 재밌네용
Dp문제 푼거 두개더있는데 문제푸느라 글을 못올렸다... ㅋㅋㅋ

오늘 연등때 올릴게요!!

아 맞다 실버3찍음 ㅋ

해당 글은 직접 공부한 내용을 정리한 글입니다
어설픈 코딩실력은 너그럽게 봐주시고 조언은 항상 환영입니다..!