[Python] 코딩 도장 - Light More Light

코딩 도장 사이트의 문제를 직접 풀어본 내용을 정리하여 올립니다.

코딩 도장에서 여러 문제를 확인할 수 있습니다.

난이도 순으로 차근차근 풀어보려 합니다.

---

[문제: Light More Light] - Lv.2

우리 학교에는 복도 불을 켜고 끄는 마부(Mabu)라는 사람이 있다.

전구마다 불을 켜고 끄는 스위치가 있다.

불이 꺼져 있을 때 스위치를 누르면 불이 켜지고 다시 스위치를 누르면 불이 꺼진다.

처음에는 모든 전구가 꺼져 있다. 마부라는 사람은 특이한 행동을 한다.

복도에 n개의 전구가 있으면, 복도를 n번 왕복한다. i번째 갈 때 그는 i로 나누어 떨어지는 위치에 있는 스위치만 누른다.

처음 위치로 돌아올 때는 아무 스위치도 건드리지 않는다.

i번째 왕복은 (이런 이상한 행동을 하면서) 복도를 한 번 갔다가 오는 것으로 정의된다. 마지막 전구의 최종 상태를 알아내자.

과연 그 전구는 켜져 있을까 아니면 꺼져 있을까?

Input

복도에 있는 n번째 전구를 나타내는 숫자가 입력된다. (2^32-1 이하의 정수가 입력된다.)

0은 입력의 끝을 의미하며 그 값은 처리하지 않는다.

Output

그 전구가 켜져 있으면 “yes”를, 꺼져 있으면 “no”를 출력한다. 테스트 케이스마다 한 줄에 하나씩 출력한다.

Sample Input

3
6241
8191
0

Sample Output

no
yes
no

출처: https://codingdojang.com/scode/429?answer_mode=hide

---

[풀이]

n = 1
lst = []

while True:
    n = int(input())
    cnt = 0
    
    if n == 0:
        for i in lst:
            print(i)
        break
        
    for i in range(1,n+1):
        if n % i == 0:
            cnt += 1

    if cnt % 2 == 0:
        lst.append("no")
    else:
        lst.append("yes")
        
    cnt=0

3
6241
8191
0
no
yes
no

마지막 전구의 on/off만 확인하므로 문제의 의도는 n의 약수의 갯수가 짝수이냐 홀수이냐이다.

for문을 통해 약수의 갯수를 모두 더해서 짝수이면 no 홀수이면 yes를 출력하게 만들었다.

---

[추천 풀이]

1의 약수={1} → 홀수개(on), 2,3,5,7,11 등 1과 자신만을 약수로 가지는 수(소수) → 짝수개(off)

12의 약수={1,2,3,4,6,12} → 짝수개(off), 15의 약수={1,3,5,15} → 짝수개(off)

16의 약수={1,2,4,8,16} → 홀수개(on), 25의 약수={1,5,25} → 홀수개(on)

즉, 1 4 9 16 25 36 49 ... 등 어떤 수의 제곱수(m^2)만이 홀수개의 약수를 가집니다 → (on)

입력된 값 n이 어떤 수의 제곱인지 확인하면 됩니다. 

다른 분이 올려주신 글인데 약수의 갯수를 파악하는데 있어서 한번 더 생각한 것이 보인다.

이 같은 논리론 다음과 같이 풀 수 있다.

while 1:
    n = int(input())
    if n == 0:
        break
    print('yes' if n**0.5 % 1 == 0 else 'no')

3
no
6241
yes
8191
no
0

아주 간결하게 풀린다.