문제 소개
처음에 모두 꺼져 있는 전구가 n개 있다고 가정해 봅시다. 첫 번째 라운드에서는 모든 전구를 켭니다. 두 번째 라운드에서는 매 두 번째 전구를 끕니다. 세 번째 라운드에서는 매 세 번째 전구의 상태를 반전시키는데, 꺼져 있으면 켜고 켜져 있으면 끕니다. 이런 식으로 i번째 라운드에서는 매 i번째 전구를 반전시키며, n번째 라운드에서는 마지막 전구 하나만 반전시킵니다.
결국 우리가 구해야 할 값은 n번의 라운드가 모두 끝난 뒤 켜져 있는 전구의 개수입니다. 예를 들어 입력이 3이라면 정답은 1이 됩니다.
예시 과정 살펴보기
- 초기 상태: 전구 3개는 모두 [꺼짐, 꺼짐, 꺼짐]입니다.
- 1라운드 후: 모든 전구를 켜므로 [켜짐, 켜짐, 켜짐]이 됩니다.
- 2라운드 후: 매 두 번째 전구를 끄므로 [켜짐, 꺼짐, 켜짐]이 됩니다.
- 3라운드 후: 매 세 번째 전구를 반전시키므로 [켜짐, 꺼짐, 꺼짐]이 됩니다.
접근 방법
이 문제의 핵심 아이디어는 의외로 간단합니다. 바로 n의 제곱근을 구해 그 값을 반환하면 됩니다. 덕분에 시뮬레이션 없이도 O(1)의 시간 복잡도로 정답을 구할 수 있습니다.
왜 제곱근일까요?
k번째 전구는 k의 약수에 해당하는 라운드에서만 상태가 변경됩니다. 대부분의 자연수는 약수가 서로 다른 두 수의 쌍으로 존재하기 때문에 상태가 짝수 번 바뀌고, 결국 처음 상태인 꺼짐으로 돌아갑니다. 그러나 완전제곱수(1, 4, 9, 16, ...)만은 √k × √k처럼 같은 약수가 짝을 이루어 약수의 개수가 홀수가 되고, 이 전구들만 최종적으로 켜진 상태로 남습니다. 따라서 n 이하의 완전제곱수의 개수, 즉 ⌊√n⌋이 곧 정답이 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};
main(){
Solution ob;
cout << (ob.bulbSwitch(3));
}
입력
3
출력
1
입력이 3일 때 함수는 √3의 정수 부분인 1을 반환합니다. 앞서 살펴본 시뮬레이션 결과와 정확히 일치하므로, 제곱근 한 줄만으로 문제를 해결할 수 있음을 확인할 수 있습니다.