백준 13909 창문 닫기 JAVA 풀이 (수학, O(1))

🔗 문제 링크

https://www.acmicpc.net/problem/13909

---

📌 문제 개요

N개의 창문이 있고 처음에는 모두 닫혀 있다.
1번째 사람부터 N번째 사람까지 순서대로 자기 번호의 배수에 해당하는 창문의 상태를 바꾼다.

• 1번째 사람 → 모든 창문 변경
• 2번째 사람 → 2, 4, 6, ... 변경
• 3번째 사람 → 3, 6, 9, ... 변경

이 과정을 모두 수행한 후, 마지막에 열려 있는 창문의 개수를 구하는 문제\

---

📌 접근 방법

이 문제는 처음 보면 시뮬레이션으로 풀 수 있을 것 같지만,
각 창문이 몇 번 상태가 바뀌는지를 생각하면 더 효율적으로 해결할 수 있다.

i번 창문은 i의 약수에 해당하는 사람들에 의해 상태가 바뀐다.

즉, i번 창문은 i의 약수 개수만큼 토글된다.

처음 상태가 닫힘이므로,

• 짝수 번 바뀌면 → 닫힘
• 홀수 번 바뀌면 → 열림

따라서 마지막에 열린 창문은 약수 개수가 홀수인 수이다.

---

📌 핵심 아이디어

일반적인 수의 약수는 (a, b) 형태로 쌍을 이루기 때문에 개수가 짝수

• 12 → (1,12), (2,6), (3,4) → 6개

 

하지만 완전제곱수는 가운데 값이 자기 자신과 짝이 된다.

• 4 → 1, 2, 4 (3개)
• 9 → 1, 3, 9 (3개)
• 16 → 1, 2, 4, 8, 16 (5개)

 

즉, 완전제곱수만 약수 개수가 홀수

 

따라서 마지막에 열린 창문 번호는 1, 4, 9, 16, 25 ... 와 같은 완전제곱수

결론적으로 N 이하의 완전제곱수 개수를 구하면 된다.

 

→ 정답 = (int) Math.sqrt(N)

---

📌 전체 코드

package no_13909;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class No13909 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        System.out.println((int) Math.sqrt(N));
    }
}

---

📄 정리

이 문제는 창문을 직접 열고 닫는 시뮬레이션 문제가 아니라,
각 창문이 몇 번 토글되는지를 약수 개수로 해석하는 것이 핵심

 

약수 개수가 홀수인 수는 완전제곱수뿐이므로,
결국 마지막에 열린 창문의 개수는 N 이하 완전제곱수 개수