[백준2193][백준][baekjoon][2193번][DynamicProgramming][DP][이친수][Python][파이썬]

문제링크

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

2193번: 이친수

문제

 

풀이

이친수(pinary number)에 관한 문제입니다. 이친수는 아래의 두가지 성질을 만족합니다.

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

정리하면 1로 시작하면서 1이 두번 들어가지 않은 이진수를 의미합니다. 이러한 특징을 갖는 N자리 이친수의 개수를 출력하는 문제입니다. 계단오르기나 비용찾기 등과 유사한 DP문제입니다. 이친수라는 단어와 개념이 친숙하지 않아 일단 먼저 경우의 수를 나열해보겠습니다.

 

N=1 : 1 (1가지)

N=2 : 10 (1가지)

N=3 : 101, 100 (2가지)

N=4 : 1010, 1000, 1001, (3가지)

N=5 : 10100, 10000, 10010, 10101, 10001 (5가지)

N=6 : 101000, 100000, 100100, 101010, 100010, 101001, 100001, 100101 (8가지)

 

나열만 했을 뿐인데 벌써 규칙이 눈에 띄네요. N자리 이친수의 종류는 N-1자리 이친수 종류와 N-2자리 이친수 종류의 합으로 표현이 되고있습니다. 이제 이 이유에 대해 정확히 알아보겠습니다.

 

N자리 이친수는 두가지로 이루어질 수 있습니다.

1. N-1자리 이친수에 0을 추가한 경우

2. N-2자리 이친수에 01을 추가한 경우

 

위와 같이 두가지로 이루어지는 이유는 이친수의 특성에 있습니다. 이친수는 0이 추가되는데는 제약이 없습니다. 따라서 1번이 가능하게 됩니다. 1이 추가될때는 제약이 따르는데, 바로 앞의 수가 1이 아니여야 한다는 것입니다. 따라서 2번이 가능하게 됩니다. 1이 추가되기 위해서는 앞의 수가 0이여야 한다는 전제가 필요한데 N-2자리 이친수에 01을 추가하는 경우가 이해 해당하게 됩니다. 2번이 N-1자리 이친수에서 1을 채울수 없는 경우를 보충하고 있습니다. 

 

소스코드

#Python

 

testcase=int(input())
 
dp=[ 0 for _ in range( 91) ]
 
for i in range(1, testcase+1):
    if i==1:
        dp[i]=1
    elif i==2:
        dp[i]=1
    else:
        dp[i]=dp[i-1]+dp[i-2]
 
print(dp[testcase])

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.

이번 포스팅에서는 python으로 작성하였지만, 추후 C와 C++ 코드도 올리도록 하겠습니다.