백준 2193번 [이친수](C++) -yes6686- 티스토리

백준 문제 풀이: 2193 [이친수]

---

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

문제 설명:

이친수는 다음과 같은 조건을 만족하는 이진수입니다:

• 0으로 시작하지 않습니다.
• 1이 두 번 연속으로 나타나지 않습니다.

정수 N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

long long dp[91]; // dp[i]: i자리 이친수의 개수

int main() {
    int n;
    cin >> n;

    // 초기값 설정
    dp[1] = 1; // 1자리 이친수: "1"
    dp[2] = 1; // 2자리 이친수: "10"

    // 점화식 계산
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n] << '\n';
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 이친수의 개수를 효율적으로 계산합니다. 이친수의 특성상, 점화식을 이용해 간결하게 계산할 수 있습니다.
• 점화식:
  • dp[i] = dp[i-1] + dp[i-2]
  • i-1자리 이친수 뒤에 "0"을 붙이는 경우와 i-2자리 이친수 뒤에 "10"을 붙이는 경우를 합산합니다.
• 구현 세부사항:
  • dp 배열을 사용해 각 자리수별 이친수의 개수를 저장
  • 1자리와 2자리 이친수는 직접 초기화
  • 점화식을 기반으로 3자리부터 N자리까지 계산
• 시간 복잡도: O(n)
  • 1부터 N까지 순차적으로 계산

---

결과

N자리 이친수의 개수를 정확히 계산합니다. 점화식을 활용해 O(n)의 시간 복잡도로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!