[백준 1904] 01타일 (C#, C++) - soo:bak

문제 링크

1904번 - 01타일

설명

길이가 N인 이진 수열을 만들 때 사용할 수 있는 조각이 1 타일과 00 타일뿐일 때, 만들 수 있는 모든 경우의 수를 구하는 문제입니다. 정답은 15746으로 나눈 나머지를 출력합니다.

접근법

길이가 n인 수열의 마지막 조각을 기준으로 나누면 두 경우만 가능합니다.

• 마지막이 1이면 앞부분은 길이 n - 1인 경우의 수와 같습니다.
• 마지막이 00이면 앞부분은 길이 n - 2인 경우의 수와 같습니다.

따라서 점화식은 다음과 같습니다.

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

초기값은 dp[1] = 1, dp[2] = 2입니다.
N이 최대 1,000,000이므로 재귀 대신 반복문으로 계산하고, 매 단계마다 15746으로 나눈 나머지를 적용합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    const int mod = 15746;
    int n = int.Parse(Console.ReadLine()!);

    if (n == 1) {
      Console.WriteLine(1);
      return;
    }

    int prev2 = 1;
    int prev1 = 2;

    for (int i = 3; i <= n; i++) {
      int current = (prev1 + prev2) % mod;
      prev2 = prev1;
      prev1 = current;
    }

    Console.WriteLine(prev1);
  }
}

C++

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

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

  const int mod = 15746;
  int n; cin >> n;

  if (n == 1) {
    cout << 1 << "\n";
    return 0;
  }

  int prev2 = 1;
  int prev1 = 2;

  for (int i = 3; i <= n; i++) {
    int current = (prev1 + prev2) % mod;
    prev2 = prev1;
    prev1 = current;
  }

  cout << prev1 << "\n";

  return 0;
}