[Python] 백준 2193번 - 이친수

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

2193번: 이친수

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 다이나믹 프로그래밍

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

 

---

 처음에 문제를 잘 못 읽어서 시간을 좀 잡아먹었다.

 

1~N (90) 까지의 숫자가 아닌

자릿수였다.

 

즉 0, 1 (1자리)

00, 01, 10, 11 (2자리)

000, 001, 010, 011, 100, ... , 111 (3자리)

 

위와 같은 방식으로 11.....11 (90자리) 까지 의 이친수를 구하는 것이었다.

 

그래서 난 각 n 자릿수의 조건을 만족하는 수 몇가지를 직접 찾아보고 규칙을 찾아야만 했다.

 

---

(앞이 0인 경우는 갯수를 세지 않으므로 바로 빼서 숫자를 카운트)

우선 n=1일땐

1

1개

 

n=2

10

11

1개

 

n=3

100

101

110

111

2개

 

n=4

1000

1001

1010

1011

1100 (이후 수는 모두 11.. 으로 시작하므로 개수를 세지 않음)

1101

...

1111

3개

 

n=5

10000

10001

10010

10011

10100

10101

10110

10111

11000 (이후 수는 모두 11.... 로 시작하므로 개수를 세지 않음)

...

11111

5개

 

즉

 

n=1 1개

n=2 1개

n=3 2개

n=4 3개

n=5 5개

n=6 8개

 

n[i] = n[i-1] + n[i-2] 의 식이 완성되는 것을 알 수 있다.

 

import sys
from collections import deque
input = sys.stdin.readline

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

처음에 dp = [0] * (n+1) 로 했다가 오류가 발생했다.

 

n=1인 경우 dp[2]가 없기 때문이다.