[백준 2193] 이친수 (C#, C++) - soo:bak

문제 링크

2193번 - 이친수

설명

0으로 시작하지 않고, 1이 연속으로 나타나지 않는 이진수를 이친수라고 합니다.

자연수 N이 주어질 때, N자리 이친수의 개수를 구하는 문제입니다.

이친수는 반드시 1로 시작해야 하고, 1 다음에는 반드시 0이 와야 한다는 제약이 있습니다.

접근법

특정 길이의 이친수 개수를 구하기 위해, 끝자리 숫자에 따라 경우를 나눕니다.

끝자리가 0인 경우, 그 앞의 숫자는 0과 1 모두 가능합니다.

끝자리가 1인 경우, 1이 연속될 수 없으므로 그 앞의 숫자는 반드시 0이어야 합니다.

이 규칙을 이용하여 점화식을 세우면, 길이 N의 이친수 개수는 길이 N-1과 N-2의 개수를 더한 값과 같습니다.

예를 들어, 1자리 이친수는 1 하나뿐이고(1개), 2자리 이친수는 10 하나뿐입니다(1개).

3자리 이친수는 100, 101 두 개(2개)이고, 4자리 이친수는 1000, 1001, 1010 세 개(3개)입니다.

이는 피보나치 수열과 동일한 패턴으로, 초기값을 1, 1로 설정하고 순차적으로 계산합니다.

N은 최대 90이므로 결과값이 매우 커질 수 있어 64비트 정수 타입을 사용해야 합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var dp = new long[91];

      dp[1] = 1;
      if (n >= 2) dp[2] = 1;

      for (var i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];

      Console.WriteLine(dp[n]);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  ll dp[91] = {0,};

  dp[1] = 1;
  if (n >= 2) dp[2] = 1;

  for (int i = 3; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];

  cout << dp[n] << "\n";

  return 0;
}