[알고리즘 수학] 원형으로 배치된 조명

문제

조명이 n개(n>2) 있고 조명은 원형으로 배치되어 있다.

각 조명마다 아래에 스위치가 있다.

각 스위치를 조작할 때마다 스위치 바로 위에 있는 것과 양쪽에 인접한 두개의 on/off 상태가 바뀐다.

처음에는 모든 조명이 꺼져 있다.

예를 들어 1,2,3 과 같이 세개의 조명이 원형으로 배치 되어 있다면 1번 아래 있는 스위치를 조작 했을 때 1과 양 옆에 있는 2와 3의 조명이 on 이 된다.

 이 때 스위치 조작 횟수를 최소화 하면서 모든 조명을 켤 수 있는 알고리즘을 설계하라.

문제출처) 길벗 - 알고리즘 퍼즐

 

문제풀이

조명이 3개 인경우에는 1,2,3 어느 스위치를 조작해도 한번에 모두 켜진다. 마찬가지로 3의 배수인 6개인 경우는 1,2,3,4,5,6 이라면 1번과 4번만 조작하면 모두 켜지는 것을 확인할 수 있다.

즉 n이 3의 배수라면 n/3 이 최소 횟수이다.

다음으로 3의 배수가 아닌 경우의 규칙만 찾으면 된다.

임의의 갯수의 전구가 있다고 가정하자.

000000....00 이 있는 경우 1번의 스위치를 조작하면 110000...01 이 된다.

다음으로 이 상태에서 2번의 스위치를 조작하면 0010000..01이 된다.

다음으로 이 상태에서 3번의 스위치를 조작하면 01010000..01이 된다.

다음으로 이 상태에서 4번의 스위치를 조작하면 01101000...01 이 된다.

이렇게 스위치를 한번씩 모두 조작하면 자신이 3번씩 동작(자신을 누를때, 자신의 왼쪽을 누를때, 자신의 오른쪽을 누를때) 하게 되므로 결국에는 모든 전구가 켜지게 된다.

그렇다면 이것 보다 더 적은 경우의 스위치를 조작하는 방법이 있는 지를 살펴 보아야 한다.

자신이 켜 지기 위해서는 자신이 홀수번 동작해야 한다. 그렇다면 1번인 경우를 제외한다면 그 다음 작은 수는 3번인 경우이다. 

1번인 경우는 전구의 갯수가 3의 배수인 경우에만 가능하므로 그 다음 작은 수는 3번 동작해야 됨을 알 수 있다. 따라서 n의 값이 3의 배수라면 n/3 의 값을 출력하고 아니라면 n을 출력하면 된다.

C++코드

cin >> n;
if(n%3==0) cout << n/3;
else cout << n