[백준 9625] BABBA (C#, C++) - soo:bak

문제 링크

9625번 - BABBA

설명

초기 화면에는 A 하나만 표시되어 있고, 버튼을 누를 때마다 A와 B가 특정 규칙에 따라 변환되는 문제입니다.

변환 규칙은 다음과 같습니다:

• A는 버튼을 누르면 B로 변합니다.
• B는 버튼을 누르면 BA로 변합니다.

버튼을 누를 때마다 이 규칙을 반복 적용했을 때,

K번 누른 후 화면에 나타나는 A의 개수와 B의 개수를 구하는 것이 목표입니다.

접근법

처음에는 A 하나만 존재합니다.

버튼을 누를 때마다 A와 B의 개수는 다음과 같은 방식으로 갱신됩니다:

• 새로운 A의 개수는 이전에 존재하던 B의 개수와 같습니다.
• 새로운 B의 개수는 이전의 A 개수와 B 개수를 더한 값이 됩니다.

이 과정을 반복하면, A와 B의 개수 변화가 피보나치 수열을 따르는 형태임을 확인할 수 있습니다.

따라서 버튼을 누를 때마다 위 규칙을 적용해 A와 B의 개수를 갱신하고,

이 과정을 K번 반복한 뒤 최종 결과를 출력하면 됩니다.

버튼을 누르는 횟수 K는 최대 45까지 주어지므로, 단순 반복문으로 충분히 계산할 수 있습니다.

Code

C#

using System;

class Program {
  static void Main() {
    int k = int.Parse(Console.ReadLine());

    int a = 1, b = 0;
    for (int i = 0; i < k; i++) {
      int t = b;
      b += a;
      a = t;
    }

    Console.WriteLine($"{a} {b}");
  }
}

C++

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

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

  int k; cin >> k;
  int a = 1, b = 0;
  while (k--) {
    int t = b;
    b += a;
    a = t;
  }
  cout << a << " " << b << "\n";
  return 0;
}