Brute force 문제3 - 시계 맞추기

문제 풀이 과정

brute force를 통한 문제임을 알고 봤음에도 풀이 방법이 명확히 떠오르지 않았는데, 가장 큰 이유는 해결 가능한 문제로 바꿔주는 조건인 각 시계는 최대 세 번까지 밖에 조작하지 못한다는 조건을 깨닫지 못했기 때문이다.
시계는 세 시간씩 움직이므로 네 번 조작하게 되면 다시 처음의 시간으로 돌아가게 되고 이 경우는 아예 조작하지 않은 경우와 같은 경우가 되므로 굳이 네 번 이상 조작할 이유는 없는 것이다.

올바른 풀이

각 시계는 세 번까지 밖에 조작하지 못하므로, 최대 경우의 수는 시계를 조작하지 않는 경우 까지 4의 10승인 백만 정도이다. 0번 시계부터 각 네 번에 해당하는 움직임을 설정하고 각 움직임마다 다음 시계로의 재귀 함수를 호출해 모든 경우의 수를 전부 확인한다.
만약 10번 시계까지 확인했을 때도 모든 시계가 12시를 가르키고 있지 않은 경우는 큰 수를 반환해서 방법이 없음을 나타내고, 모두 12시를 가르키는 경우에는 0을 반환해서 재귀 함수를 따라 올라가면서 모든 조작 회수가 더해지게끔 한다.

문제풀이 과정에서의 핵심 아이디어

• 조작 횟수의 최대값을 생각하기
• 각 조작 횟수 별 재귀 함수 호출
• 조작한 경우 별도 함수인 push를 통해 시간 변경