문제
서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.
예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,
- 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
- 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
- 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)
결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.
입력
첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.
출력
마지막에 열려 있는 창문의 개수를 출력한다.
풀이
창문 i는 자기 자신의 약수 개수만큼 열리고 닫힌다. 상태가 홀수 번 바뀌면 마지막에 열려 있고 짝수 번 바뀌면 닫히는데, 약수 개수가 홀수인 수는 완전제곱수뿐이다.
그래서 정답은 1부터 N까지의 완전제곱수 개수, 즉 floor(sqrt(N))가 된다. 현재 코드는 이 관찰을 그대로 사용해 시뮬레이션 없이 한 번에 답을 계산한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
long N = Integer.parseInt(br.readLine());
long result = (long) Math.sqrt(N);
System.out.println(result);
}
}복잡도
- 시간 복잡도: 제곱수 개수를 바로 계산하므로 이다.
- 공간 복잡도: 추가 자료구조를 사용하지 않으므로 이다.
마무리
반복문을 돌려 창문을 직접 뒤집지 않아도 된다. 마지막에 열린 창문은 완전제곱수 번호뿐이라는 관찰이 곧 답이다.
