[백준] 2226 이진수 (골드 4)

1으로 시작하는 그룹의 개수를 구하는 것이 문제이지만, 

이를 풀기 위해서 0으로 시작하는 그룹의 개수 또한 dp로 저장하며 계산에 활용했습니다.

 

찾아낸 패턴은 아래와 같습니다.

 

<패턴 1> 

 

0으로 시작하는 이진수의 배열을 dp_0(n)이라 하고,

1로 시작하는 이진수의 배열을 dp_1(n)이라 하면

 

dp_0(n) = dp_0(n-2) + dp_1(n-2) + dp_0(n-1)

dp_1(n) = dp_1(n-2) + dp_0(n-2) + dp_1(n-1) 

 

여기서 + 연산은 파이썬에서의 문자열 concatenation 연산자로 사용했습니다.

 

<패턴 2> 

 

0으로 시작하는 이진수 배열의 n번째 수의 그룹개수를 dp_0_group(n)이라 하고,

1으로 시작하는 이진수 배열의 n번째 수의 그룹개수를 dp_1_group(n)이라 하면

 

n이 홀수일 때

          dp_0_group(n) = dp_0_group(n-2) + dp_1_group(n-2) + dp_0_group(n-1)

          dp_1_group(n) = dp_1_group(n-2) + dp_0_group(n-2) + dp_1_group(n-1) -1

 

n이 짝수일 때

          dp_0_group(n) = dp_0_group(n-2) + dp_1_group(n-2) + dp_0_group(n-1) -1

          dp_1_group(n) = dp_1_group(n-2) + dp_0_group(n-2) + dp_1_group(n-1)

 

여기서 + 연산은 일반적인 자연수 덧셈 연산자로 사용했습니다.

 

 

 

예를 들어서 생각해봅시다.

 

문제의 규칙에 따르면 아래와 같이 수들이 자라나게 됩니다.

0 -> 10 -> 0110 -> 10010110 -> 0110100110010110 -> ...

1 -> 01  -> 1001 -> 01101001 -> 1001011001101001 -> 01101001100101101001011001101001 -> ...

 

 

dp_0(5) = 0110100110010110 = 0110 1001 10010110 => dp_0(3) + dp_1(3) + dp_0(4)

dp_1(6) = 01101001100101101001011001101001 =  01101001 10010110 1001011001101001

              => dp_1(4) + dp_0(4) + dp_1(5)

 

 dp_0_group(5) = dp_0_group(3) + dp_1_group(3) + dp_0_group(4) = 2 + 1 + 3 = 6

dp_1_group(6) = dp_1_group(4) + dp_0_group(4) + dp_1_group(5) = 3 + 3 + 5 = 11

 

 

정답 코드는 아래와 같습니다.

 

N = int(input().rstrip())

dp_0 = [0 for _ in range(1001)] ## 0을 시작으로 자라나는 이진수의 그룹 개수
dp_1 = [0 for _ in range(1001)] ## 1을 시작으로 자라나는 이진수의 그룹 개수

dp_0[1] = 1
dp_1[1] = 0

dp_0[2] = 1
dp_1[2] = 1

for i in range(3, N+1):
    
    ## i가 짝수인 경우
    ## 0시작은 더한 것에서 1빼기
    ## 1시작은 그대로
    ## 그대로 더해준다.
    if i % 2 == 0:
        dp_0[i] = dp_0[i-2] + dp_1[i-2] + dp_0[i-1] - 1 
        dp_1[i] = dp_1[i-2] + dp_0[i-2] + dp_1[i-1]

    ## i가 홀수인 경우
    ## 0시작은 그대로
    ## 1시작은 더한 것에서 1빼기
    else:
        dp_0[i] = dp_0[i-2] + dp_1[i-2] + dp_0[i-1]
        dp_1[i] = dp_1[i-2] + dp_0[i-2] + dp_1[i-1] - 1

print(dp_1[N])