처음에 모두 켜져 있는 n개의 전구가 있는 방과 벽면에 부착된 4개의 버튼이 있다고 가정해 보겠습니다. 정확히 m번의 버튼 조작을 수행한 후, n개의 전구가 가질 수 있는 서로 다른 상태의 가짓수를 구하는 것이 이 문제의 목표입니다.
전구에는 [1, 2, 3, ..., n]과 같이 번호가 매겨져 있으며, 4개의 버튼은 각각 다음과 같은 기능을 합니다.
- 모든 전구의 상태를 반전(켜짐 ↔ 꺼짐)시킵니다.
- 짝수 번호의 전구를 반전시킵니다.
- 홀수 번호의 전구를 반전시킵니다.
- (3k + 1)번째 전구를 반전시킵니다. (k = 0, 1, 2, ...)
예를 들어 n = 3, m = 1이라면 가능한 결과 상태는 다음 4가지입니다.
[꺼짐, 켜짐, 꺼짐], [켜짐, 꺼짐, 켜짐], [꺼짐, 꺼짐, 꺼짐], [꺼짐, 켜짐, 켜짐]
접근 방법
이 문제의 핵심은 같은 버튼을 두 번 누르면 원래 상태로 되돌아간다는 점입니다. 즉, 최종 결과는 각 버튼을 누른 횟수가 홀수인지 짝수인지에만 의존하므로, m이 3 이상일 때는 m = 3인 경우와 결과가 완전히 같습니다. 또한 전구의 최종 상태는 첫 3개의 전구만으로 결정되기 때문에 고려해야 할 경우의 수가 크게 줄어듭니다.
이러한 성질을 활용하면 복잡한 시뮬레이션 없이 다음과 같은 규칙으로 곧바로 답을 도출할 수 있습니다.
- n이 0이거나 m이 0이면 1을 반환합니다. (아무 변화도 일어나지 않음)
- n이 1이면 2를 반환합니다. (켜짐 또는 꺼짐 두 가지)
- n이 2라면 m이 1일 때 3을, 그렇지 않으면 4를 반환합니다.
- m이 1이면 4를 반환합니다.
- m이 2이면 7을, 그 외의 경우(m ≥ 3)에는 8을 반환합니다.
C++ 구현 예제
아래 코드는 위 규칙을 그대로 구현한 것으로, 입력 크기와 무관하게 O(1) 시간에 답을 계산할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int flipLights(int n, int m) {
if (m == 0 || n == 0) return 1;
if (n == 1) return 2;
if (n == 2) return m == 1? 3:4;
if (m == 1) return 4;
return m == 2? 7:8;
}
};
main(){
Solution ob;
cout << (ob.flipLights(3, 1));
}입력
3 1
출력
4
n = 3, m = 1인 경우 위에서 확인한 것처럼 서로 다른 전구 상태는 총 4가지이므로, 프로그램은 올바르게 4를 출력합니다.