백준 2193번 : 이친수 (Python)

문제 : www.acmicpc.net/problem/2193

2193번: 이친수

 

풀이

맨앞의 수는 무조건 1이다. 그 다음부터는 1이 연속 두번 이상 나오는 경우를 제외해야 하므로 남은 자리에 수를 대입할 때 1과 0을 대입하지 않고 01과 0을 대입하는 것으로 계산한다.

 

01은 자리를 한번에 두개씩 차지하므로 01이 들어가는 만큼 빈자리의 수를 줄이고 조합으로 해결한다. 우선 맨 앞자리 수는 고정이므로 빈자리의 수 n-1을 k에 저장한다. 01이 들어가는 수 만큼 반복문을 사용하여 result에 더한다. i는 01의 개수이며 최대 k//2개까지 대입될 수 있다. 01의 개수(i)만큼 빈자리가 줄어드므로 k-i를 빈자리의 값으로 계산한 뒤 a에 저장한다. a~i까지 곱한 값에 i~1까지 곱한 값을 나누면 빈자리에 01을 대입하는 경우의 수가 된다.

계산시 곱해지는 값은 미리 dp에 저장해둔다.

 

 

n = int(input())

dp = [1, 1]
for i in range(2,n):
    dp.append(i*dp[i-1])


if n==1 or n==2:
    result = 1

else:
    result = 1
    k = n-1

    for i in range(1,k//2+1):
    	a = k-i
        result += (dp[a] // dp[a-i])// dp[i]

print(result)