[BaekJoon] #13909 - 창문 닫기 [Java][C++]

문제 링크

---

1. 아이디어

$1$부터 $N$까지 각 수의 배수 번째 창문의 상태를 바꿀 경우 열린 창문의 개수를 구하는 문제로 임의의 $M$번 창문에 대해 해당 창문을 열거나 닫을 수 있는 수는 $M$의 약수들만 가능하다. 처음에 모든 창문이 닫혀 있으므로 창문이 열려있으려면 약수의 개수가 홀수이면 되며 약수의 개수가 홀수인 수는 1, 4, 9 같은 제곱수들만 가능하다. 따라서 $N$보다 작거나 같은 제곱수들의 개수를 찾으면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(\sqrt{N})$	$O(1)$

($N$ = 입력값 n)

---

3. 코드

풀이 [Java][C++]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int cnt = 1;
        while (cnt * cnt <= n) {
            cnt++;
        }

        System.out.println(cnt - 1);
    }
}

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

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

    int n;
    cin >> n;

    int cnt = 1;
    while (cnt * cnt <= n) {
        cnt++;
    }

    cout << cnt - 1;
}

---