[algorithm] 백준 13909 - 창문 닫기

[algorithm] 백준 13909 - 창문 닫기

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 13909번 문제 - 창문 닫기 에 대한 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 13909

 

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

 

13909번: 창문 닫기

 

문제 해석

 

실습실의 창문이 열려있는 경우 그 조건이 무엇인가를 차근차근 생각해 봅시다.

대략 9 번째 창문까지만 잘 생각해 보면 어떤 경우에 창문이 열려있는지를 파악할 수 있을 겁니다.

힌트 : 약수의 개수를 잘 살펴보세요.

 

풀이

 

n = int(input())

count = 0
i = 1

while i*i <= n:
    i += 1
    count += 1 

print(count)

 

풀이 해석 및 팁

 

문제에서 궁극적으로 원하는 것은 주어진 범위 안에 존재하는 제곱수의 개수를 찾는 것입니다.

창문이 열려있는 경우를 보면 해당 창문의 순번인 숫자의 약수가 홀수개인 것이 확인됩니다.

열려있는 창문의 순번은 1, 4, 9, 16 ... 인데 약수가 홀수이려면 제곱수인 경우에만 가능합니다.

즉, 제곱수의 개수를 찾기만 하면 열려있는 창문의 수를 금방 파악할 수 있게 됩니다.

---

여기까지 백준 13909번 창문 닫기의 풀이였습니다.

 

문제 출제자의 의도를 파악할 수 있는 통찰력을 기르기 위해 문제에서 주어지는 규칙이나 조건들의

 

특징에 대해 차근차근 생각해 보는 습관을 들이면 좋을 것 같습니다.

 

감사합니다.