[백준 5948] Bad Random Numbers (C#, C++) - soo:bak

문제 링크

5948번 - Bad Random Numbers

설명

네 자리 정수가 주어졌을 때, 그 수를 일정한 규칙에 따라 반복적으로 갱신해 나가며,

처음으로 같은 수가 다시 등장하기까지의 반복 횟수를 구하는 문제입니다.

갱신 방식은 다음과 같습니다:

• 현재 수의 백의 자리와 십의 자리를 추출하여 두 자리 수를 만듭니다.
• 그 수를 제곱하여 새로운 수로 갱신합니다.
• 이전에 등장한 적이 있는 수가 다시 나타나면 과정을 종료합니다.

이 방식은 난수 생성 기법 중 하나인 middle square 방식을 응용한 구조로,

유한한 수의 상태 공간 안에서 수열이 언제 순환을 시작하는지를 판단하는 문제입니다.

참고 : Middle-Square 방식 난수 생성 알고리듬의 원리와 한계 - soo:bak

접근법

• 첫 수를 입력받고, 최대 4자리 수 범위인 0부터 9999까지를 방문 체크할 수 있도록 비트셋을 준비합니다.
• 매 반복마다 백의 자리와 십의 자리 숫자를 추출하여 두 자리 수로 만들고, 이를 제곱하여 다음 수로 설정합니다.
• 수가 처음으로 중복되는 순간 반복을 종료하고, 지금까지의 반복 횟수를 출력합니다.

Code

C#

using System;
using System.Collections;

class Program {
  static void Main() {
    var visited = new BitArray(10000);
    int n = int.Parse(Console.ReadLine());
    int cnt = 0;

    while (!visited[n]) {
      visited[n] = true;

      int hundreds = (n / 100) % 10;
      int tens = (n / 10) % 10;
      int middle = hundreds * 10 + tens;

      n = middle * middle;
      cnt++;
    }

    Console.WriteLine(cnt);
  }
}

C++

#include <bits/stdc++.h>

using namespace std;

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

  bitset<10000> visited;

  int n; cin >> n;

  int cnt = 0;
  while (!visited[n]) {
    visited[n] = true;
    int mid = (n / 100 % 10) * 10 + (n / 10 % 10);
    n = mid * mid;
    cnt++;
  }

  cout << cnt << "\n";

  return 0;
}