13989번 창문 닫기 | python

오랜만에 알고리즘을 공부하다보니 감을 다 잃은 거 같아서, 물론 예전과 큰 차이가 없겠지만...ㅎ

감을 찾기 위해 문제를 풀고 그 중 생각을 좀 필요로 한다고 판단되는 문제를 써보려고 한다.

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

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)이 주어진다.

 

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

 

---

문제를 딱 읽었을 때에는 리스트를 이용하여 푸는 방식인줄 알고 리스트를 만들어 코드를 작성했다. 그러나, 리스트를 이용한 풀이를 진행하게 되면 메모리 초과로 인해 문제를 해결할 수 없었다.
이를 해결하기 위해, 다양한 방식을 고민했고 그 중에서 리스트 인덱스에서 1의 값(창문이 열린 상태)에 해당하는 인덱스의 공통점을 조사했다. 조사한 결과, 모두 제곱수라는 것을 알 수 있었다. 이러한 결론을 통해 주어진 숫자 n보다 작거나 같은 자연수 중, 해당 값의 제곱수가 1 ~ n 범위 안에 들어가 있으면 창문이 열린다는 결론에 다가갈 수 있다. 해당 관점을 가지고 아래의 코드를 작성했다.

import sys

input = sys.stdin.readline

answer = 0
n = int(input())
for number in range(1, n + 1):
    if number ** 2 <= n:
        answer += 1
print(answer)

1부터 n까지 돌면서 제곱수를 찾으면 된다. (물론 도착 범위를 sqrt(n) + 1로 지정해도 되는 것으로 보인다.)