문제
서강대학교 컴퓨터공학과 실습실 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)이 주어진다.
출력
마지막에 열려 있는 창문의 개수를 출력한다.
예제
나의 풀이1 (실패)
N = int(input())
windows = [0]+[1]*(N)
for i in range(2, N+1):
for j in range(i, N+1, i):
if windows[j] == 0:
windows[j] = 1
else:
windows[j] = 0
print(sum(windows))1부터 모든 경우의 수를 계산하려고 했는데 당연히 메모리 초과가 발생했다.
다른 사람의 풀이
N = int(input())
print(int(N**0.5))- 창문이 열려 있으려면 홀수 번 변경되어야 한다.
- 어떤 수가 홀수 개의 약수를 가지려면, 완전제곱수여야 한다. (1, 4, 9, 16...)
- 짝수 개의 약수를 가지는 수는 약수 쌍이 존재하지만, 제곱수는 중간에 같은 약수가 한 번만 등장하기 때문
- 예를 들어 9의 약수 → (1, 9), (3, 3) → 3이 한 번만 등장 → 홀수 개 약수
- N 이하의 완전제곱수의 개수를 세려면 N의 제곱근을 계산하면 된다.
회고
- 꽤나 오랫동안 고민했던 문제인데 결국 스스로 접근법을 찾아내지는 못했다.
- 전혀 접근법을 모르겠을 땐 어떤 방식이로든 결과를 출력해서 규칙을 찾아보자. 여기서 힌트를 얻을 수도 있다.
- 그래도 새로운 아이디어를 얻을 수 있는 문제였다.