[백준 6359] 만취한 상범 (C#, C++) - soo:bak

문제 링크

6359번 - 만취한 상범

설명

1부터 N까지 방 번호에 대해 문을 여닫는 규칙을 반복 적용한 후, 마지막에 열려 있는 방의 수를 계산하는 문제입니다.

상범이는n개의 방을 대상으로하여 다음과 같은 방식으로 라운드를 진행합니다:

• 1 라운드: 모든 방을 엽니다.
• 2 라운드: 2의 배수 방만 닫습니다.
• 3 라운드: 3의 배수 방만 상태를 반전시킵니다.
• ...
• n 라운드: n의 배수 방만 상태를 반전시킵니다.

각 방의 상태는 라운드마다 반전되므로,

해당 방 번호의 약수 개수만큼 상태가 바뀌게 됩니다.

즉, 약수의 개수가 홀수인 방 번호만 최종적으로 열려 있게 되며,

그러한 수는 자기 자신을 제곱한 수(= 완전 제곱수)뿐입니다.

접근법

• 1부터 n까지의 정수 중에서 제곱수인 수의 개수를 세면 됩니다.
• 예를 들어 n = 100일 경우, \(1^2\)부터 \(10^2\)까지 총 10개의 제곱수가 존재하므로 답은 10입니다.
• 이를 위해 입력받은 n에 대해 sqrt(n)의 정수 부분을 구하면 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    int t = int.Parse(Console.ReadLine());
    while (t-- > 0) {
      int n = int.Parse(Console.ReadLine());
      Console.WriteLine((int)Math.Floor(Math.Sqrt(n)));
    }
  }
}

C++

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

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

  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    cout << (int)sqrt(n) << "\n";
  }

  return 0;
}