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

문제 링크

---

1. 문제 풀이

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

---

2. 코드

1. 풀이 [Java]

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);
    }
}

2. 풀이 [C++]

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

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

    int n;
    cin >> n;

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

    cout << cnt - 1;
}

---