[백준 17869] Simple Collatz Sequence (C#, C++) - soo:bak

문제 링크

17869번 - Simple Collatz Sequence

설명

시작 정수 n (1 ≤ n ≤ 2³² - 1)이 주어지는 상황에서, 특정 규칙에 따라 수열을 만들어 1에 도달할 때까지 걸리는 단계 수를 구하는 문제입니다.

수열 생성 규칙:

• 현재 값이 짝수면 2로 나눔
• 현재 값이 홀수면 1을 더함

접근법

주어진 규칙대로 n이 1이 될 때까지 반복하며 단계 수를 세면 됩니다.

각 단계에서 현재 값이 짝수인지 홀수인지 판별하여 규칙을 적용합니다.

짝수인 경우 2로 나누어 값을 절반으로 줄이고, 홀수인 경우 1을 더하여 짝수로 만듭니다.

홀수에 1을 더하면 항상 짝수가 되므로, 홀수가 연속으로 나올 수 없습니다.

n이 1이 되면 반복을 종료하고 지금까지 센 단계 수를 출력합니다.

---

Code

C#

using System;

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

      while (n != 1) {
        steps++;
        if (n % 2 == 0) n /= 2;
        else n += 1;
      }

      Console.WriteLine(steps);
    }
  }
}

C++

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

typedef long long ll;

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

  ll n; cin >> n;
  int steps = 0;

  while (n != 1) {
    steps++;
    if (n % 2 == 0) n /= 2;
    else n += 1;
  }

  cout << steps << "\n";

  return 0;
}