[알고스팟] CLOCKSYNC - Synchronizing Clocks (C++)

문제

algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

풀이

 

이번 문제의 핵심은 두 가지이다.

 

• 시계는 4번 돌리면 결국 원상태로 돌아온다.

     즉, 4번 이상 시계를 돌릴 필요는 없다.

 

• 스위치를 누르는 순서는 중요하지 않다.

       예를 들어, 0번과 1번 스위치를 누른다고 할 때 무엇을 먼저 누르든 결과는 같다.

 

int pushedNum[10];          //스위치를 누른 횟수를 저장
int clockState[16];            //현재 시계의 상태를 저장
vector<vector<int>> clockSwitch;  //스위치마다 연결된 시계를 저장

 

void pushSwitch(int switchIdx)

 누를 스위치 번호를 받아와 눌러주는 함수

 

void recoverClockState(int switchIdx)

 다시 스위치를 한번도 누르지 않은, 원래 상태로 돌려주는 함수. 

 

위의 함수를 이용하여 모든 경우의 수를 확인해보는 FindMinswitchNum를 구현하자.

void FindMinswitchNum(int switchIdx,int cnt)

 매개변수 switchIdx로 몇 번째 스위치를 누를지를, cnt로 지금까지 누른 스위치 횟수를 전달한다.

switchIdx가 10보다 작을 경우에만 switchIdx을 +1해 주어 바로 다시 재귀호출하는데, 그 이유는 해당 스위치를 누르지 않고 다음 스위치들을 누르는 경우를 구현하기 위해서 이다.

 

다음은 for문을 3번까지만 반복하며 해당 스위치를 눌러주고(pushSwitch호출) 카운트 값(cnt)을 ++해준다.

 

다음은 모든 시계가 12시를 가리키는지 확인하는 for문을 돌아준다. 이때 만약 모든 값이 12여서 k가 16까지 도달한 경우 mininum에 결과 값을 저장하고 recoverClockState를 호출하여 clockState를 현재 함수의 호출 전으로 복구시켜준다. 복구시켜주지 않는다면 스위치가 눌러진 상태로 값이 계속 남아 이상한 답이 나오게 된다. 

 

아직 모든 값이 도달하지 못했다면 FindMinswitchNum(switchIdx+1,cnt) 로 재귀 호출한다. 만약 cnt가 minimum-1보다 크거나 같다면 cnt는 다음에 minimum보다 크거나 같아지므로 더 이상 최솟값이 아니게 되어 계산을 지속할 필요가 없어진다. 따라서 for문을 탈출하여 다음 재귀를 호출하거나 for문을 끝까지 돌지 않는다.

 

스위치를 3번 눌러봐도 정답이 아니라면 for문이 끝나 recoverClockState 를 호출해 복구한 후, 함수를 종료한다.

 

풀이는 다해놓고 오류를 찾는데만 2시간이 걸린 것 같다... (코드만 보면 토할 것 같은 기분) 분명히 논리적으로는 맞는데 이상한 답이 나와서 고생 고생하며 코드를 다 뜯어보니, 시계의 수가 16개인데 10개로 해두고 정답을 찾는 for문을 돌리고 있었다...

 

알고리즘을 풀 때 고정된 수라면 상수화 합시다!!

 

코드