백준 2226: 이진수

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

2226번: 이진수

 

풀이

작은 N에 대한 문자열을 찾아내 규칙을 파악해보도록 하겠습니다.

1	2	3	4	5
1	01	1001	01101001	1001011001101001

이런 식으로 나오게 됩니다. N에 대한 문자열 S를 앞쪽의 반과 뒤쪽의 반으로 나누어보겠습니다.

N	2	3	4	5
앞쪽 반	0	10	0110	10010110
뒤쪽 반	1	01	1001	01101001

앞쪽의 반도 그 전 단계를 이루는 앞쪽의 반에서부터 온 것이며, 뒤쪽의 반도 똑같이 그렇게 만들어진 것입니다. 첫 시작이 0과 1이고 0은 10으로, 1은 01로 되기 때문에 N번째 문자열 S의 앞쪽 반과 뒤쪽 반의 XOR값을 취하면 $11\cdots1_{(2)}$이 됩니다. 

이에 착안하여 생각을 해보았을 때, N-1번째의 앞쪽 반을 A, 뒤쪽 반을 B라 하면 N번째 문자열은 ABBA 꼴로 표현이 됩니다.

N	2	3	4	5
앞쪽 반의 연속 0 그룹	1	1	2	3
뒤쪽 반의 연속 0 그룹	0	1	1	3
합계	1	2(but 실제는 1)	3	6(but 실제는 5)

위의 표를 토대로 생각했을 때 규칙을 파악하실 수 있을 것이고, 증명은 생각해봤을 때 그리 어렵지 않으니 생략하겠습니다.

 

이런 적당한 관찰들을 바탕으로 dp[N]=(N번째 문자열에서 연속된 0 그룹의 개수)가 되는 수열의 점화식을 구할 수 있습니다.

$$dp[N]=\begin{cases} 2\times dp[N-1]+1 & (N\equiv 0 \ (\mathrm{mod} \ 2)) \\ 2\times dp[N-1]-1 & (N\equiv 1\ (\mathrm{mod} \ 2)) \end{cases}$$

 

코드

위와 같은 풀이로 짠 코드입니다.

이 문제에서는 N의 범위가 1부터 1000까지인지라 정수형의 범위가 없는 Python을 사용하였습니다.

n=int(input())
dp=[0, 0, 1]
for i in range(3, n+1):
    if i%2==0: dp.append(dp[i-1]*2+1)
    else: dp.append(dp[i-1]*2-1)
print(dp[n])

 

감사합니다.