[백준] 이친수

문제보기 - https://www.acmicpc.net/problem/2193

문제명    - 이친수

난이도    - S3

문제유형 - DP

풀이일자 - 25.03.22

 

📌 문제 탐색하기

• 이친수는 다음과 같은 조건을 만족하는 이진수임
  1. 0으로 시작하지 않음
  2. 1이 두 번 연속으로 나타나지 않음 (즉, 11을 부분 문자열로 갖지 않음)
• N(1 ≤ N ≤ 90)이 입력으로 주어짐
• 입력으로 주어진 N자리 이친수의 개수를 출력해야 함
  • N = 1 -> {1} -> 1개
  • N = 2 -> {10} -> 1개
  • N = 3 -> {100, 101} -> 2개
  • N = 4 -> {1000, 1001, 1010} -> 3개
  • N = 5 -> {10000, 10001, 10010, 10100, 10101} -> 5개

 

🛠 시간복잡도 확인

• DP 활용하여 O(n)에 해결가능!

 

📌 코드 설계하기

1. N값 입력받기
   • sys.stdin.readline()
2. DP 배열 정의 -> i자리 이친수의 개수를 저장할 배열
   • dp = [0] * (N + 1)
3. 초기값 설정 -> 1,2자리 
4. 점화식 적용 -> dp[n] = dp[n-1] + dp[n-2]
5. 결과 출력

 

📌 정답 코드(1회차)

import sys

# 1. N 입력 받기
N = int(sys.stdin.readline())

# 2. DP 배열 정의
dp = [0] * (N + 1)

# 3. 초기값 설정
dp[1] = 1  # 1자리 이친수는 '1'
if N > 1:
    dp[2] = 1  # 2자리 이친수는 '10'

# 4. 점화식 적용
for i in range(3, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

# 5. 결과 출력
print(dp[N])