[백준/2193/파이썬] 이친수

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

2193번: 이친수

 

Problem

• N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오

조건

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

SOL)

이진수는 1또는 0으로 끝난다. 

이친수는 11이 두번 연속으로 나타나지 않는다.

1. 끝에 1이오면, 다음으로 올 수는 무적권 0 ex) 101 -> 1010(o),1011(x)
2. 끝에 0이오면 ,다음으로 올 수는 1 or 0 ex) 100 -> 1001(o) , 1000(o)

이 문제를 만약 선형적으로 푼다고하면, n자리이므로, n이 0or 1로 끝날 수 있고, 0으로 끝난다면 거기서 또 2가지 경우가 생기므로, 2^n꼴으로 늘어나기 때문에, 완전탐색으로는 불가능하다.

 

따라서, DP로 접근을 해야함. 재귀적인 관계이기 때문에.

생각보다 규칙은 쉽게 나온다.

이친수

• F(1) = 1
• F(2) = 10
• F(3) = 100 , 101
• F(4) = 1001 1010 ,1000
• F(5) = 10000, 10001 , 10010, 10100 10101
• F(n) = F(n-2) + F(n-1) (단, N은 자릿수)

점화식이 아니더라도, DP table로 생각하면, DP[1][n] DP[0][n] 이런식으로 생각해서 1로 끝날 떄, 2로 끝날때 경우의 수를 세어주고 더해주면 더 와닿게 풀 수 도 있을거같긴하다.

 

#Top -down
def sol(n):
    if n==1:
        return 1
    if n==2:
        return 1
    if DP[n] !=0:
        return DP[n]
    else:
        DP[n] = sol(n-2) + sol(n-1)
        return DP[n]

DP=[0]*91
N = int(input())

print(sol(N))