[BOJ 2193] 백준 2193 이친수

문제

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

2193번: 이친수

 

 

접근 조건

• 기본적인 dp 문제이다.
• dp 테이블을 정하자 이때 dp[i]를 길이 i일 때 가질 수 있는 이친수의 가짓수로 정의할 것이다.
• 이친수의 조건에 따라 길이 1, 2일때의 이친수는 각각 1, 10으로 1개씩이 될 것이다.
• 길이 3이후의 이친수의 가짓수를 살펴보면 다음과 같다.
  • 3일때 가질 수 있는 이친수는 101, 100으로 2가지이다.
  • 4일때 가질 수 있는 이친수는 1010, 1001, 1000으로 3가지이다.
  • 5일때 가질 수 있는 이친수는 10101, 10100, 10010, 10001, 10000으로 5가지이다.
• 계속 하다보면 익숙한 패턴이 보일 것이다. 바로 피보나치 수열 패턴과 일치한다.
• 피보나치 수열 패턴으로 점화식을 구성하면 dp[i] = dp[i - 2] + dp[i - 1]이 되므로 이를 그대로 구현하면 된다.

 

 

답안 코드

N = int(input())

if N < 3:
    print(1)
    exit(0)

dp = [0]*(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])

• N 이 3 미만이면 언제나 1을 가지기 때문에 1을 출력하게 하고 종료하는 예외를 추가하면 나머지는 접근 방법에서 구한 점화식으로 모두 구할 수 있다.