[백준 06359] 만취한 상범 [Java]

문제

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.

그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5 ≤ n ≤ 100)이 주어진다.

출력

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

6359번: 만취한 상범

---

풀이

N개의 방에 대해 1~N의 배수에 해당하는 문을 열고 닫을 때 최종적으로 열린 문의 갯수를 구하는 문제다.

최종적으로 열린 문의 갯수는 N의 약수의 갯수와 연관 있다.

 

K번(1~N)의 라운드를 진행하며, K(i)일 때 i의 배수를 반전시킨다.

이 과정에서 i의 약수들(j1, j2, j3, ...)이 만약 홀수개라면 K(i)일 때 i번째 문을 열 것이다. (i - 1번째는 닫힌 상태이므로)

만약 약수의 갯수가 짝수개라면, 이전 라운드에서 i번째 방문은 열린 상태에서 K(i)라운드로 들어와 닫힌 상태가 된다.

 

즉, K라운드 이후의 열린 방문의 갯수는, N이하의 수 중 약수를 홀수개 가지는 수들의 갯수와 동일하다.

이는 제곱수의 갯수를 의미하므로 sqrt(N)과 동일하다.

따라서 주어진 N에 대해 sqrt(N)을 출력하면 된다.

---

소스코드 

보기