[백준알고리즘] 2193번: 이친수 -Python

[백준알고리즘] 2193번: 이친수 -Python

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

2193번: 이친수

이진수에서 0으로 시작하지 않는 N자리 수 중에서 1이 두 번 연속으로 등장하지 않는 수를 이친수라고 한다고 한다.

 

즉 N-1자리의 이친수에서 1개의 값 0 또는 1을 추가할 때 1을 추가하기 위해서는 이전 수가 반드시 0이어야 한다. 반대로 0을 추가할 때에는 이전 수가 0 또는 1 모두 상관없게 된다.

 

따라서 각 인덱스의 위치에 0이 추가될 수 있는 경우의 수를 갖는 리스트와 1이 추가될 수 있는 경우의 수를 갖는 리스트를 준비하고, 0으로 시작할 수 없기 때문에 1번째 자리의 수에 해당하는 값은 0이 올 수 있는 경우의 수는 0개, 1이 올 수 있는 경우의 수는 1개로 주고 시작한다.

 

이후 두 번째 자리의 수를 추가할 때 1을 추가하기 위해서는 첫 번째 자리의 수가 0일 때만 추가할 수 있어 table_0[1]의 값을 갖게 되는데, 이 값은 0이기 때문에 가능한 경우의 수는 0개다. 하지만 0을 추가하기 위해선 첫 번째 자리의 수가 0일 때, 1일 때 모두 추가할 수 있어 table_0[1] + table[1] 이 되지만 0으로 시작하는 경우의 수는 0이기 때문에 1개가 된다. 따라서 두 번째 자리의 수까지 채우게 되면 아래와 같은 상태가 된다.

table_0 = [0, 0, 1( = table_0[1] + table_1[1])]

table_1 = [0, 1, 0( = table_0[1])]

 

마찬가지 방식으로 세 번째 자리의 수를 추가할 때에도 0이 올 수 있는 경우의 수는 두 번째 자리에 0이 온 경우의 수와 1이 온 경우의 수의 합이 되며, 1이 올 수 있는 경우의 수는 두 번째 자리에 0이 올 수 있는 경우의 수와 같다.

 

따라서 점화식은 아래와 같이 구했다.

table_0[i] = table_0[i-1] + table_1[i-1]

table_1[i] = table_0[i-1]

 

import sys

N = int(sys.stdin.readline())
table_0 = [0, 0]
table_1 = [0, 1]

for i in range(1, N):
    table_1.append(table_0[i])
    table_0.append(table_0[i] + table_1[i])

sys.stdout.write(str(table_1[-1] + table_0[-1]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다