[알고리즘/DP] 2193번 : 이친수 - python

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

2193번: 이친수

 

---

• 문제
• 소요시간: 16분 50초

---

• 설계하기(접근방법) 

1. 입력받기

n을 입력받는다

 

2. 구현하기

이친수를 써보니 피보나치 수열의 형태가 나타났다

왜

dp[n] = dp[n-1] + dp[n-2]의 형태가 나타날까???

 

 

새로운 이친수를 구할 때 

우리는 끝이 0 아니면 1인 케이스로 나눌 수 있다

 

끝이 0인 케이스는

 

dp[n-1]의 케이스에서 어느곳이든 0을 붙일 수 있기 때문에 

dp[n-1] 개다

 

그렇다면

끝이 1인 케이스는 어떨까?

 

이친수의 성질은 1이 연속으로 나타날 수 없으니

끝이 1이라는 의미는

끝이 01이라는 의미와 같다

 

그렇다면 01인 케이스는 어떻게 구할까??

dp[n-2]의 케이스에서 0을 붙인 케이스에다가

그냥 1을 붙인것과 같다

 

즉 dp[n-2]에서 0을 붙인 케이스를 구해주면 된다

앞서 말했듯이 0은 어느곳이든 붙일 수 있으니

끝이 1인 케이스는 dp[n-2]개다

 

이 둘을 합하면

dp[n] = dp[n-1] + dp[n-2]이다

 

 

3. 출력하기

dp[n]을 출력한다

 

---

• 코드(출력)

n = int(input())

if n == 1:
    print(1)
else:
    dp = [0 for _ in range(n + 1)]
    dp[1] = 1
    dp[2] = 1

    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[n])

---

• 얻어갈 부분

1. 이친수가 나타나는 이유를 이해했다