2193: 이친수

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

2193번: 이친수

설명

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

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

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

핵심 아이디어

• 다이나믹 프로그래밍
• n = 1 ~ n= 5 일 때까지 직접 계산해서 점화식을 구하자!

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

• dp[i] = d[i-1] + dp[i-2]

코드 구현

# 답안 1

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 91 # dp테이블 초기화

dp[1] = 1 # 작은 문제 계산
dp[2] = 1
for i in range(3, n+1):
	dp[i] = dp[i-1] + dp[i-2]
print(dp[n])

---

처음 코드를 짰을 때 indexError 가 발생해서 뭐 때문이지 고민했었다. 처음 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (n+1) # dp테이블 초기화

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 테이블을 초기화 할 때, dp = [0] * (n+1) 을 해줬는데, 이렇게 하게 될 경우 n=1 일때 dp[2]에 접근하려고 하기 때문이다. 코드에서는 dp[2] = 1로 설정하려는데, n=1일 경우 dp 테이블의 크기가 2(dp[0], dp[1])이기 때문에 dp[2]에 접근할 수 없습니다. 따라서 다음과 같이 코드를 수정하여 해결할 수 있었습니다.

 

# 답안2

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (n+1) # dp테이블 초기화

dp[1] = 1 # 작은 문제 계산
for i in range(2, n+1):
	dp[i] = dp[i-1] + dp[i-2]
print(dp[n])