[BOJ] 이친수(2193) - PYTHON

길이 N이 주어질 때, 1이 2개 이상 연속해서 나오지 않으며, 길이가 N인 2진수의 개수를 구하는 문제다. 단 2진수는 1로 시작해야 한다.

시간 복잡도 : O(N)

2193번: 이친수

---

풀이 방법

2진수의 길이가 1씩 늘어난다고 하면, 바로 직전에 만들었던 이친수에 0을 붙여서 이친수를 만들 수 있고, 전전에 만들었던 이친수에 01을 붙여 이친수를 새로 만들 수 있다. 이렇게 만들면 이친수가 중복 없이 생성된다.

N	이친수
1	1
2	10
3	101,100
4	1001, 1010, 1000
5	10001, 10101, 10010, 10100, 10000

  이와 같이 이친수는 점화식이 다음과 같은 수열이 된다.

즉 피보나치 수열이 정답이 된다.

---

코드

N = int(input())
arr = [[0, 0] for _ in range(91)]
 
arr[1] = [0, 1] 
arr[2] = [1, 0] 
arr[3] = [1, 1] 
arr[4] = [2, 1] 
arr[5] = [3, 2]
for i in range(3, N + 1):
    arr[i] = [sum(arr[i - 1]), arr[i - 1][0]]
print(sum(arr[N]))

 

주석 추가

N = int(input())
arr = [[0, 0] for _ in range(91)]  # N은 최대 90
 
# 0으로끝나는 수의 갯수, 1로 끝나는 수의 갯수
arr[1] = [0, 1]  # x // 1
arr[2] = [1, 0]  # 10 // x
arr[3] = [1, 1]  # 100 // 101
arr[4] = [2, 1]  # 1000 1010  // 1001
arr[5] = [3, 2]  # 10000 10100 10010 // 10001 10101
for i in range(3, N + 1):
    arr[i] = [sum(arr[i - 1]), arr[i - 1][0]]
# 0으로 끝나는 수는 이전에 나온 이친수에 0을 더하고
# 1로 끝나는 수는 이전에 나온 0으로 끝나는 이친수에 1을 더한다
 
print(sum(arr[N]))  # 정답은 배열의 N번째 인덱스 값들의 합
 

0으로 끝나는 수는 sum(arr[N - 1])의 값과 똑같고 1로 끝나는 수는 arr[N - 1][0] = sum(arr[N - 2])값과 똑같다.
끝나는 자릿수에 집중에 문제를 해결하다 보니 피보나치 수열이지만 2번 계산하도록 식이 나왔다.

---

실행 결과