문제 소개
방 안에 n개의 토글 스위치가 있고, 사람도 n명이 있다고 가정해 봅시다. 이들은 다음과 같은 규칙에 따라 순서대로 스위치를 조작합니다.
- 1번 사람: 들어와서 모든 스위치를 누릅니다.
- 2번 사람: 2의 배수 번호(2, 4, 6, ...)에 해당하는 스위치를 누릅니다.
- i번 사람: i의 배수 번호에 해당하는 스위치를 누릅니다. 이 과정이 n번 사람까지 반복됩니다.
모든 사람이 지나간 후, 최종적으로 켜져 있는(ON) 스위치가 몇 개인지 구하는 것이 이 문제의 목표입니다.
예시로 이해하기
n = 5일 때를 살펴보겠습니다. 처음에는 모든 전구가 꺼져 있는 상태입니다: [0, 0, 0, 0, 0]
- 1번 사람이 지나간 후: [1, 1, 1, 1, 1]
- 2번 사람이 지나간 후: [1, 0, 1, 0, 1]
- 3번 사람이 지나간 후: [1, 0, 0, 0, 1]
- 4번 사람이 지나간 후: [1, 0, 0, 1, 1]
- 5번 사람이 지나간 후: [1, 0, 0, 1, 0]
결국 ON 상태로 남아 있는 전구는 2개입니다.
핵심 아이디어: 왜 답이 √n일까?
k번째 전구는 자신의 번호를 나눌 수 있는 사람(i가 k의 약수일 때)마다 한 번씩 켜지거나 꺼집니다. 즉, k번 전구는 k의 약수 개수만큼 조작됩니다.
약수는 보통 짝으로 나타납니다. 예를 들어 12의 약수는 (1,12), (2,6), (3,4)처럼 서로 곱해서 12가 되는 쌍으로 묶이므로, 조작 횟수는 항상 짝수가 되어 마지막엔 꺼진 상태로 끝납니다.
하지만 완전제곱수(1, 4, 9, 16, ...)만 예외입니다. √k × √k = k이므로 √k라는 약수가 자기 자신과 짝을 이루어, 약수 개수가 홀수가 됩니다. 따라서 최종적으로 켜진 전구는 n 이하의 완전제곱수의 개수, 즉 ⌊√n⌋개입니다.
이진 탐색으로 정수 제곱근 구하기
부동소수점 오차 없이 ⌊√n⌋을 정확히 구하기 위해 이진 탐색(binary search)을 사용할 수 있습니다. 탐색 범위를 좁혀 가면서 mid² ≤ n < (mid+1)²을 만족하는 값을 찾으면 됩니다.
파이썬 구현 코드
def solve(n):
l, r = 0, n
while l <= r:
mid = l + (r - l) // 2
# mid² ≤ n < (mid+1)² 인 경우 mid가 정답
if mid * mid <= n < (mid + 1) * (mid + 1):
return mid
elif n < mid * mid:
r = mid
else:
l = mid + 1
n = 5
print(solve(n))실행 결과
입력:
5
출력:
2
마무리
이 문제는 단순 시뮬레이션으로도 O(n²)에 풀 수 있지만, 약수의 성질을 활용하면 O(log n)의 이진 탐색으로 매우 효율적으로 해결할 수 있습니다. 코딩 테스트에서 자주 등장하는 '전구 스위치(Bulb Switcher)' 유형의 대표적인 문제이니, 완전제곱수와 약수 개수의 관계를 꼭 기억해 두시길 바랍니다.