[백준/Python] 13909 - 창문 닫기

문제

서강대학교 컴퓨터공학과 실습실 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)이 주어진다.

출력

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

풀이
문제만 읽었을 때는 어려울 것 없어보이지만, N의 범위에 주목해야 하는 문제
단순히 반복문으로 문제를 접근하면 무조건 메모리초과가 발생한다

n을 대충 25 정도로 잡고 1부터 25까지의 결과값들을 출력해보면 다음과 같이 나타난다
1112222233333334444444445
이 패턴의 특징은 제곱수를 기점으로 1씩 증가한다는 것이다
인덱스가 $1^2$일 때 1이 시작되고 $2^2$일 때 2가 시작된다
제곱수가 아닌 수의 경우에는 루트를 씌워 정수 부분만 사용하면 되는 것이다
따라서 아주 간단하게 n에 루트를 씌운 값에 소수 부분을 제거해주면 정답이 된다

코드

import sys, math

n = int(sys.stdin.readline())

print(int(math.sqrt(n)))