문제
algospot.com :: CLOCKSYNC
Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록
algospot.com
풀이
버튼을 누르는 순서는 중요하지 않지만, 4번 누르면 시계가 원래대로 돌아오기 때문에 O(4^10)인 완전 탐색이 가능하다.
우선 버튼을 눌렀을 때 시간이 변하는 시계들을 다음과 같이 정리해주자.
각 배열의 첫번째 요소는 배열의 길이를 의미한다.
버튼을 누르는 횟수는 4회 미만이므로 버튼을 눌렀을 때 시계를 바로 업데이트 하는 것이 아닌 다음 버튼을 누르는 Recursive Call을 해서 분기를 나누어야 한다.
마지막 버튼에 도달한 경우에만 업데이트된 시계가 전부 12시를 가르키는지 확인해주자.
만약 1개라도 12시가 아니라면 INF를 반환해 최솟값 갱신을 무효화 하자.
소스코드
'PS > Algospot (for. 알고리즘 문제해결 전략)' 카테고리의 다른 글
| [Algospot] BOARDCOVER [C/C++] (1) | 2024.03.14 |
|---|