[종만북] CLOCKSYNC - Synchronizing Clocks (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-CLOCKSYNC

 

 

풀이

  시계 자체에 초점을 맞추면 답이 안나온다. 스위치가 10개 밖에 없다는 부분에 초점을 맞춰보자. 결국 시계는 4번 돌면 제자리다.

 

  따라서 각 10개의 스위치는 3번 이상 누를 일이 없고, 그럼 O(C x 4^10)으로 처리가 가능함을 알 수 있다. 즉, 시계가 몇칸인지는 상관 없고, 그냥 스위치가 10개이고 각각 최대 3번까지 누를 수 있으니 4x4x... 를 해주면 되는 것이다. 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int[][] MAPPING = {
            {0, 1, 2},
            {3, 7, 9, 11},
            {4, 10, 14, 15},
            {0, 4, 5, 6, 7},
            {6, 7, 8, 10, 12},
            {0, 2, 14, 15},
            {3, 14, 15},
            {4, 5, 7, 14, 15},
            {1, 2, 3, 4, 5},
            {3, 4, 5, 9, 13}
    };
    private static int[] clocks = new int[16];
    private int min;

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        int c = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (c-->0) {
            sb.append(main.solution()).append('\n');
        }
        System.out.print(sb);
    }

    private int solution() throws Exception {
        setupClocks();
        synchronizeClocks(0, 0);

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private void setupClocks() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        min = Integer.MAX_VALUE;

        for (int i = 0; i < 16; i++) {
            clocks[i] = Integer.parseInt(st.nextToken());
        }
    }

    private void synchronizeClocks(int cnt, int mappingIdx) {
        if (mappingIdx == 10) {
            if (min > cnt && isAllClocks12()) {
                min = cnt;
            }
            return;
        }

        synchronizeClocks(cnt, mappingIdx+1);
        for (int i = 1; i <= 3; i++) {
            pressSwitch(mappingIdx, i, true);
            synchronizeClocks(cnt+i, mappingIdx+1);
            pressSwitch(mappingIdx, i, false);
        }
    }

    private void pressSwitch(int mappingIdx, int nth, boolean isClockwise) {
        for (int i = 0; i < MAPPING[mappingIdx].length; i++) {
            if (isClockwise) {
                clocks[MAPPING[mappingIdx][i]] += 3 * nth;
                if (clocks[MAPPING[mappingIdx][i]] > 12)
                    clocks[MAPPING[mappingIdx][i]] -= 12;
            } else {
                clocks[MAPPING[mappingIdx][i]] -= 3 * nth;
                if (clocks[MAPPING[mappingIdx][i]] <= 0)
                    clocks[MAPPING[mappingIdx][i]] += 12;
            }
        }
    }

    private boolean isAllClocks12() {
        for (int i = 0; i < 16; i++) {
            if (clocks[i] != 12) return false;
        }
        return true;
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.