[파이썬] [백준 - 2193번] 이친수(DP)

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

2193번: 이친수

[풀이]

먼저 조건을 생각해보면 처음 숫자는 무조건 1이 나와야 하고, 1은 연속해서 나올 수가 없고, 0에는 아무런 제약이 없다. 끝에 숫자가 1이면 그 다음은 무조건 0이라는 사실과 끝에 숫자가 0이면 0 또는 1 두가지가 나올 수 있다.

(처음에는 헷갈려서 그림을 그리면서 해보았다..)

끝에 숫자가 0인것과 1인것을 구분해서 구해보면

각각의 숫자는 피보나치 수열을 따른 다는 것을 알 수 있다(0,1,1,2,3,5,…)

따라서 Dynamic Programming으로 각각 구해서 해결할 수 있었다.

 

n은 1부터 가능하므로 배열을 만들때 주의해서 index 오류를 범하지 않도록 해야 한다.

 

[해결]

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