[백준/Python] 13909 창문 닫기

‣​ 문제 링크

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

 

13909번: 창문 닫기

---

‣​ 접근 방법

창문의 상태가 바뀌는 것은 해당 창문 번호의 약수의 개수와 관련이 있다.

예를 들어, 12번 창문의 경우 1, 2, 3, 4, 6, 12의 6개 약수가 있으므로 6번 상태가 바뀌게 된다.

그럼 0에서 6번 상태가 바뀐 12는 최종적으로 어떤 상태일까?

아래는 12번째의 창문의 상태가 자신의 약수번째 사람일 경우 어떻게 바뀔지 표로 나타낸 것이다.

1	2	3	4	6	12
열림	닫힘	열림	닫힘	열림	닫힘

 

아직 뭔가를 확정적으로 생각하기에는 조금 애매하다.

추가적인 예시로 문제와 동일하게  24번 창문의 경우를 생각해보자.

24의 약수는 1, 2, 3, 4, 6, 8, 12, 24로 8개의 약수가 있으므로 8번 상태가 바뀌게 된다.

그럼 0에서 8번 상태가 바뀐 24는 최종적으로 어떤 상태일까?

1	2	3	4	6	8	12	24
열림	닫힘	열림	닫힘	열림	닫힘	열림	닫힘

 

앞선 두 예시를 통해, 우리는 짝수개의 약수를 지니면 최종적으로 닫힌 상태임을 파악할 수 있다.

그럼 반대로, 약수가 홀수개라면, 열림 상태임을 알 수 있다.

 

약수의 개수가 홀수인 경우는 제곱수(1², 2², 3², 4², ...​)인 경우이다.

주어진 n 이하의 제곱수의 개수를 구하려면, n의 제곱근을 구하면 된다.

예를 들어 n이 25일 경우, 제곱근의 개수는 √25인 5개가 된다.

 

따라서 문제를 해결하기 위해서는 주어진 n까지의 제곱수의 개수를 세면 된다.

 

---

‣​ 풀이

위 접근 방법을 생각하고 문제를 풀면 코드는 아래와 같다.

import sys
n = int(sys.stdin.readline())
print(int(n**0.5))

---

‣​ 사족

n 이하의 제곱수의 개수를 구하려면, n의 제곱근을 구하면 된다는 점을 정말 오랜만에 생각해본 것 같다.

나중에 까먹을 거 같아서 내가 종종 읽는 내 블로그에 작성해 둔다.

아무튼 도움이 되었길 바람-