[Python] 백준 13909번 (창문 닫기) [실버5]

https://www.acmicpc.net/problem/13909

N의 범위가 21억이고 시간 제한이 1초라서 시뮬레이션으로 풀면 무조건 시간 초과가 뜰 것 같다.

 

하지만 문제만 읽고서는 한 눈에 규칙이 보이지 않아 처음에는 나이브하게 N을 하나씩 늘려갔다.

# 1
# 1

# 1 0
# 1 2

# 1 0 0
# 1 2 3

# 1 0 0 1
# 1 2 3 4

# 1 0 0 1 0
# 1 2 3 4 5

# 1 0 0 1 0 0
# 1 2 3 4 5 6

# 1 0 0 1 0 0 0
# 1 2 3 4 5 6 7

# 1 0 0 1 0 0 0 0
# 1 2 3 4 5 6 7 8

# 1 0 0 1 0 0 0 0 1
# 1 2 3 4 5 6 7 8 9

뭔가 규칙이 보이긴 한 것 같다. 해당 창문의 번호가 어떤 수의 제곱수이면 창문이 열려 있는 것 같다.

 

하지만 왜 그런지에 대해서는 아직 잘 모르겠다. 다시 차근차근 창문이 열려 있을 때와 닫혀 있을 때의 행동 횟수를 비교해보자.

 

창문은 초기에 모두 닫혀있다. 창문이 열려 있을 때는 행동을 홀수번 한다. 반대로 창문이 닫혀 있을 때는 행동을 짝수번 한다.

 

또한, 모든 창문은 자신의 약수의 개수만큼 행동을 당한다. 그렇다면 약수의 개수가 홀수개여야 창문이 열려있다는 말이다.

 

일단 모든 수는 1과 자기 자신을 약수로 가진다. 그리고 약수의 순서로 볼때 항상 i번째 약수와 n-i+1번째 약수의 곱은 해당 수가 된다.

 

예를 들어 12의 약수는 [1, 2, 3, 4, 6, 12]인데 1*12, 2*6, 3*4는 모두 12가 된다는 말이다. 다른 예로 16의 약수는 [1, 2, 4, 8, 16]인데 이처럼 약수의 개수가 홀수이면 반드시 가운데에 위치한 약수는 자기 자신을 제곱해야 해당 수가 된다.

 

즉, 약수의 개수가 홀수라는 말은 반드시 해당 수의 제곱근이 약수로 포함되어 있다는 의미가 된다.

 

정답

import sys

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

count = 0
num = 1
while num**2 <= N:
    count += 1
    num += 1

sys.stdout.write(str(count) + "\n")

 

풀이

1. 열려 있는 창문의 개수를 나타낼 count와 제곱근 숫자를 나타낼 num을 초기화한다.

count = 0
num = 1

 

2. 만약 num의 제곱이 N보다 크게 된다면 반복문을 빠져나온다. 결과적으로 N보다 작은 제곱수의 개수를 찾으면 된다.

while num**2 <= N:
    count += 1
    num += 1