[백준/baekjoon] 13909번 창문 닫기 (파이썬)

내 제출

- 첫 제출은 틀렸었다(복잡도 n^2인 중첩 for문 쓴 첫 제출 ↓)

# 창문의 개수와 사람의 수 n이 주어진다.
n = int(input())

# 처음에 모든 창문은 닫혀 있다.
window = [False] * n

for num in range(1, n+1):
    for i in range(num, n, num):
        window[i-1] = not window[i-1]

print(window.count(True))

- 이 문제 메모리 제한이 64MB다.

- 다른 문제는 128MB는 됐는데 작다. 그런데도 나는 for문을 중첩시켜서 계산했다.

- 여튼 그래서 N이 매우 큰 경우에는 안 맞는 코드인지 메모리 초과가 떴다.

- 사실 정답이 아닌 걸 보고 새 코드를 작성하는 데에 시간이 한참 걸렸다. 딱히 좋은 아이디어가 생각나지 않았음.

- 이면지에 창문 그려서 닫고 - 열고 순서대로 작성해봤다.

- 그리고 이 문제의 난이도를 다시 보니까 갑자기 좋은 생각이 났다.

- 사람이 홀수명이 조작하면 창문이 열린다는 거...

- 근데 또 홀수명이 조작하는 경우가 언제인지는 한참 종이에 쓰고 알아차렸다.

import math

n = int(input())

# sqrt 함수를 사용하여 주어진 n이하의 완전제곱수 개수를 계산.
result = int(math.sqrt(n))

print(result)

- 코드는 넘나 간단하다.

 

문제 접근 / 풀이

- 문제의 핵심은 '어떤 창문이 마지막에 열려 있는가'이다.

- 창문이 열리거나 닫히는 것은 해당 창문 번호의 약수에 해당하는 사람들이 행동할 때 발생한다.

- 물론 0명이 조작하는 경우는 안 된다(창문의 디폴트 값이 닫혀있기 때문에 한 번은 열려야 함.)

- 그리고 창문이 최종적으로 열려 있으려면, 창문을 조작하는 사람의 수가 홀수여야 한다.

- 창문을 조작하는 사람의 수가 홀수인 경우는 그 창문의 번호가 완전제곱수인 경우이다

- 완전제곱수를 제외한 다른 숫자들은 모두 짝수 개의 약수를 가지기 때문.

- 여기에 대해서 좀 더 주저리 설명 ↓

- 완전 제곱수 : 1, 4, 9, 16등..

 

- 완전제곱수가 아닌 숫자들 중 8을 예로 들면,

- 약수 하나를 구하면(ex.2) 그 약수에 매칭되는 또 다른 약수(ex.4)가 있다 => 필연적으로 2개씩 약수가 생겨난다

 

- 하지만 완전제곱수는 약수가 되는 제곱근 1개로 인해 전체 약수의 개수가 홀수 개일수 있다.

- 즉, 1부터 n까지의 창문들 중 n의 약수 창문들이 열리거나 닫히고,

- 그 열리거나 닫히는 창문들 중에서 완전제곱수 번호의 창문들만 최종적으로 열려있게 된다.

- 그래서 N이하의 완전제곱수의 개수를 찾는 코드를 작성하면 된다 => 이는 sqrt(N)을 계산하여 내림한 값이다.

 

결과

- 백준 문제 난이도를 띄울 수 있는 방법이 있어서 적용해봤다.

- 알고는 있었는데 여태 쉬운 문제들만 풀었는데도 바로 못 맞은 게 꽤 되네 쩝...

- 그래두 천리길도 한 걸음부터라고...? 늘겠지~~?!

- 이번엔 2-try.