[백준 24296] ЛИНИЯ (C#, C++) - soo:bak

문제 링크

24296번 - ЛИНИЯ

설명

매번 인접한 학생 사이에 한 명씩 끼어드는 과정을 여러 번 거친 뒤의 인원 수 N이 주어질 때, 처음 인원의 최소값을 구하는 문제입니다.

접근법

한 번 끼어들기가 끝나면 인원이 두 배에서 하나를 뺀 값이 되어 항상 홀수입니다.

따라서 현재 인원이 홀수인 동안 역연산을 반복하고, 짝수가 되면 더 이상 되돌릴 수 없으므로 그 값이 최소 초기 인원입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    while (n % 2 == 1)
      n = (n + 1) / 2;
    Console.WriteLine(n);
  }
}

C++

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

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

  int n; cin >> n;
  while (n % 2 == 1)
    n = (n + 1) / 2;
  cout << n << "\n";

  return 0;
}