[백준/Python] 13909 창문 닫기

[백준/Python] 13909 창문 닫기

정답 코드 및 설명

import math

N = int(input())
print(int(math.sqrt(N)))

문제의 규칙

• 각 사람은 자신의 번호에 해당하는 배수의 창문을 열거나 닫는다.
• 예를 들어, 1번 사람이 모든 창문을 조작하고 2번 사람은 2,4,6,... 번 창문을 조작한다.
• 창문은 처음에 모두 닫혀 있으며, 한 번 조작할 때마다 열렸다가 닫혔다가를 반복한다.

창문이 열리는 조건

• 이 문제는 열린 창문의 갯수를 세는 문제이다. 때문에 열리는 조건에 집중할 필요성이 있다.
• 창문이 열리려면 홀수 번 조작되어야 한다. 짝수 번 조작되면 다시 닫히기 때문이다.
• 각 창문이 몇 번 조작되는 지는 그 창문 번호의 약수의 갯수에 달려있다
  - 예를 들어 6번 창문은 1,2,3,6 의 배수이므로 4번 조작된다
  • 9번 창문이라면 1,3,9 의 배수 이므로 3번 조작된다.

완전 제곱수

• 완전 제곱수는 그 수의 제곱근이 정수인 수를 의미한다. 예를 들어 1^2 인 1, 2^2 인 4, 3^2 인 9, 4^2 인 16 등이 완전 제곱수이다.
• 완전 제곱수는 홀수 개의 약수를 가지고 있다. 이는 제곱근이 자기 자신을 포함하는 유일한 약수가 되기 때문이다.
  - 예를 들어서 16의 약수는 1,2,4,8,16 이다. 이 중 4는 제곱근이고, 약수의 총 갯수는 5개(홀수) 이다.
• 따라서 완전 제곱수에 해당하는 창문 만이 홀수 번 조작된다. 이 뜻은 완전 제곱수에 해당하는 창문이 바로 열려 있게 된다.

문제 해결

• 열려 있는 창문을 찾기 위해서 N이하의 완전 제곱수의 개수를 세면 된다.
• 이는 N의 제곱근을 계산하고, 그 정수 부분을 취함으로써 얻을 수 있다.
• 예를 들어서 N이 24라면 24의 제곱은 약 4.9 이다. 이 경우 1,4,9,16 은 24 이하의 완전 제곱수이므로 열려있는 창문은 4개가 된다.