처음에 켜져 있는 n개의 조명과 벽에 4개의 버튼이 있는 방이 있다고 가정합니다. 버튼에 대해 정확히 m개의 알 수 없는 작업을 수행한 후 n개의 조명 상태가 얼마나 많은 다른 종류가 될 수 있는지를 반환해야 합니다. 따라서 n개의 조명이 숫자 [1, 2, 3 ..., n]으로 표시되어 있다고 가정하고 이 4개 버튼의 기능은 다음과 같습니다. -
- 모든 조명을 뒤집습니다.
- 짝수로 조명을 뒤집습니다.
- 홀수로 조명을 뒤집습니다.
- (3k + 1) 숫자로 조명 뒤집기, k =0, 1, 2, ...
이제 n =3이고 m =1이면 [꺼짐, 켜기, 끄기], [켜기, 끄기, 켜기], [끄기, 끄기, 끄기], [끄기, 켜기, 켜기]의 4가지 작업이 있습니다. ]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n이 0이거나 m이 0이면 1을 반환합니다.
- n이 1이면 2를 반환
- n이 2이면 3을 반환하고 m이 1이면 4를 반환합니다.
- m이 1이면 4를 반환합니다.
- m이 2이면 7을 반환하고, 그렇지 않으면 8을 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#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