[Baekjoon/JAVA] 13909번 - 창문 닫기

[백준] Baekjoon Online Judge

문제로 이동

 

문제

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

 

입력

첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

 

출력

마지막에 열려 있는 창문의 개수를 출력한다.

 

---

예제 입력	예제 출력
3	1
24	4

---

풀이

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

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

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

 

1:	1	- 1개
2:	11	10	- 1개
3:	111	101	100	- 1개
4:	1111	1010	1000	1001	- 2개
5:	11111	10101	10001	10011	10010	- 2개
6:	111111	101010	100011	100111	100101	100100	- 2개
7:	1111111	1010101	1000111	1001111	1001011	1001001	1001000	- 2개
8:	11111111 10101010 10001110 10011111 10010111 10010011 10010001 10010000	- 2개
9:	11111111 10101010 10001110 10011111 10010111 10010011 1001000 10010000 100100001 - 3개

직접 창문을 열고 닫아보면 위와 같은 모습이 나온다. 여기서 1, 4, 9번째 창문이 열려 있다는 것을 알 수 있는데, 이 숫자들은 어떤 수의 제곱인 수이다. 즉, 마지막까지 열려 있는 창문의 수는 N보다 작은 제곱인 수의 개수와 같다.