S3 2193. 이친수

문제 보기 :  2193번: 이친수

---

문제

• 정답률 : 41%

---

작성 코드

T = int(input())
before = {0:0,1:1}
n = 1
while n < T:
    next = {0:0,1:0}
    next[0]=before[0]+before[1]
    next[1]=before[0]
    before = next
    n += 1
print(sum(before.values()))

---

풀이

끝이 뭔지를 보는게 중요할 것 같다는 생각을 했다.
그래서 길이가 1인 경우부터 5인 경우까지 확인하면서 갯수를 세고 규칙을 찾았다.

길이가 1이면, 1 만 가능. 즉, key(끝 숫자)가 0,1인 딕셔너리로 나타내면 {0:0,1:1}
길이가 2이면, 10 만 가능. 즉, {0:1,1:0}
길이가 3이면, 100 / 101 가능. {0:1,1:1}
길이가 4이면, 1000 / 1001 / 1010 가능. {0:2,1:1}
길이가 5이면, 10000 / 10001 / 10010 / 10100 / 10101 가능. {0:3,1:2}

다음턴 next = {0:0,1:0}에서 next[0]=before[0]+before[1], next[1]=before[0]

끝이 0이면 전에 나온 경우의 수 리턴값으로 받음.
끝이 1이면 전에 나온 경우의 수 중 끝 값이 0인 경우만 리턴.