[알고리즘 문제해결 전략]6장. 무식하게 풀기_⑤

CLOCKSYNC in algospot

---

problem

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • CLOCKSYNC
  • 10000ms
  • 65536kb
  • 7597
  • 2989 (39%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • IOI 1994
  • 보기

문제

그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.

시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.

0	0, 1, 2
1	3, 7, 9, 11
2	4, 10, 14, 15
3	0, 4, 5, 6, 7
4	6, 7, 8, 10, 12
5	0, 2, 14, 15
6	3, 14, 15
7	4, 5, 7, 14, 15
8	1, 2, 3, 4, 5
9	3, 4, 5, 9, 13

시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자. 시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.

입력

첫 줄에 테스트 케이스의 개수 C (<= 30) 가 주어진다. 
각 테스트 케이스는 한 줄에 16개의 정수로 주어지며, 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9 중 하나로 표현한다.

출력

각 테스트 케이스당 한 줄을 출력한다. 시계들을 모두 12시로 돌려놓기 위해 눌러야 할 스위치의 최소 수를 출력한다. 만약 이것이 불가능할 경우 -1 을 출력한다.

예제 입력

2
12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12 
12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6

예제 출력

2
9

Thinking

 완전 탐색을 하기위해 그 방법을 모색해보자. 같은 스위치를 4번 눌리면 한바퀴를 도는 것과 동일하다. 즉 같은 스위치를 몇번 누르던 상관이 없다는 것이다. 그리고 스위치를 누르는 순서가 어찌되던 그 결과는 동일하다. 그러므로 스위치를 누르는 순서에 신경을 쓸 필요도 없다. 

 이 문제를 앞서 해결한 BOARDCOVER문제와 비슷하게 생각해서 풀어보자. 하나의 스위치를 몇번누를지 결정하고 다음스위치를 누르는 횟수를 정하는 형식으로 문제를 풀어보자.

Important Code

void solve(int* clock, int switch_num, int now) {
 
    if (ans <= now)return;    // 만약 이제까지 구한 스위치을 누른 횟수가 이전에 구해놓은 정답보다 크다면 탐색을 멈춘다.
    if (switch_num == 10) {//만약 0에서 9까지의 모든 스위치를 탐색하여 10으로 올 경우 
        if (is_same(clock) == 0)return;// 모든 시계바늘이 12를 가리키는지 확인한다.
        ans = min(ans, now);//더 작은 값이 정답이 된다.
        return;
    }
    for (int i = 0; i < 4; i++) {//switch_num에서 스위치를 누를 횟수를 정한다
        clock_wise(clock,switch_num,i);//정해진 스위치의 횟수만큼 버튼을 눌러준다.
        solve(clock,switch_num + 1,now+i);//다음 스위치를 누를 횟수를 정하로 간다.
        Cnt_clock_wise(clock,switch_num,i);//원상복귀시켜 (시계반대방향으로 회전) 다음 횟수에 대하여 답을 구할 수 있게한다.
    }
}

Solve

success

출처

---

문제:  algosport CLOCKSYNC문제( 링크 )