백준(Python) 2193번 이친수 풀이

Python으로 구현한 2193번 이친수 문제 풀이입니다.

 

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

2193번: 이친수

---

# 1 : 1 (1가지)
# 2 : 10 (1가지)
# 3 : 101, 100 (2가지)
# 4 : 1000, 1010, 1001 (3가지)
# 5 : 10000, 10001, 10010, 10100, 10101 (5가지)

def solution(n) :
	if n == 1 or n == 2 :
		return 1
	if n == 3 :
		return 2
	if dp[n] != 0 :
		return dp[n]
	dp[n] = solution(n-1) + solution(n-2)
	return dp[n]

n = int(input())
dp = [0] * (n + 1)
print(solution(n))

 

1. 아래의 두가지 성질을 만족하는 n자리 이친수의 개수는 1가지, 1가지, 2가지, 3가지, 5가지, ... 이다.

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

 

2. 즉, 0101, 011 와 같은 형태는 이친수가 될 수 없다.

 

3. n이 주어졌을 때, n자리 이친수의 개수는 dp 테이블의 이전 요소 두 값의 합임을 알 수 있다.