이진수 C++ - 백준 2226

https://acmicpc.net/problem/2226

dp문제.

문제 접근

각 이진수들을 살펴보면 항상 자기 자신 앞에 반대 수가 붙게 된다.

이 성질은 모양 뭉탱이에게도 성립하는데,

예를 들어

$0110$ 은 항상 $10010110$이 된다.

그리고 이를 통해 알 수 있는 규칙이 있는데,

$0$이 하나 있는 부분은 항상 $0$이 두 개 있는 부분을 만들고

$0$이 두 개 있는 부분은 항상 $0$이 하나 있는 부분을 두 배로,

$0$이 두 개 있는 부분을 만든다.

따라서 다음과 같은 점화식이 나온다.

$DP_{i,0}$를 0이 한 개 있는 부분,

$DP_{i,1}$를 0이 두 개 있는 부분이라고 하자

$DP_{i,0}=2\cdot DP_{i-1,1}$
$DP_{i,1}=DP_{i-1,1}+DP_{i-1,0}$

이다.

범위가 $2^{1000}$이므로 Big Int를 다루기 쉬운 파이썬에서 코드를 작성했다.

코드는 다음과 같다.

n=int(input())
dp=[[0]*2 for _ in range(1000)]
dp[1][0]=1
for i in range(2,n):
    dp[i][0]=2*dp[i-1][1]
    dp[i][1]=dp[i-1][0]+dp[i-1][1]
print(dp[n-1][0]+dp[n-1][1])