[백준/Python] 2193번 이친수

문제

 

https://www.acmicpc.net/problem/2193

2193번: 이친수

---

Algorithm

1번 규칙에 의해 N=1일때 이친수는 1개[1]이고,2번 규칙에 의해 N=2일때 이친수는 1개[10]가 된다. N=3일때는 N=2일때 이친수의 끝자리가 0이므로 [100,101]이 나올수 있으므로 2개이다. N=4일때는 N=3일때 이친수의 끝자리가 0일때는 [1000,1001]이 나오고, 1일때는 [1010]이 나오게 된다. N이 점점 커져서 k일때를 가정해보자. N=k일때는 N=k-1일때 이친수의 끝자리가 0,1인 경우로 나누어서 생각해보자. 끝자리가 1이면 N=k일때 끝자리는 0으로 정해지므로 N=k-1일때 끝자리가 1인 개수와 동일하다. 끝자리가 0이면 N=k일때 끝자리는 0,1이 가능하므로 N = k-1일때 끝자리가 0인 개수의 2배가 된다. 따라서 N =k일때 끝자리가 1인 이친수는 N = k-1일때 끝자리가 0인개수이고, N = k일때 끝자리가 0인 이친수는 N = k-1일때 이친수의 개수와 같다.

O 풀이과정

o N을 입력 받음, N이 3일때 끝자리가 0인것의 개수가 1이므로 c0=1, 끝자리가 1인것의 개수가 1이므로 c1=1을 선언

o N = 1,2,3일때는 1,1,2를 출력한다

o N= 1,2,3이 아니면 반복문 실행

   - 반복문이 실행되면 N이 4이상이기 때문에 N-3까지 실행하도록 설정한다.

   - 임시로 값을 받아줄 temp1,temp0를 선언하고, 각각 c1,c0의 값을 넣어준다.

   - c0, 즉 끝자리가 0인 이친수의 개수는 temp0+temp1개 이므로 값을 넣어주고 c1, 즉 끝자리가 1인 이친수의 개수는 temp0개 이므로 값을 넣어준다.

o 반복문이 끝나면, c1+c0의 값을 출력한다.

---

 

 

Code

input = __import__('sys').stdin.readline

n = int(input())

c1 = 1 
c0 = 1

if(n==1):print(1)
elif(n==2):print(1)
elif(n==3):print(2)
else:
    for i in range(n-3):
        temp1 = c1
        temp0 = c0
        c0 = temp1+temp0
        c1 = temp0
    print(c1+c0)