[Java] 알고스팟 : CLOCKSYNC

문제 링크

1.

완전탐색(브루트포스) 문제

이것으로 완전탐색 문제는 마무리가 되는데, 뭔가 대략적인 틀이 보이는 것 같으면서도 여전히 어렵다.

 

2.

자세한 풀이는 책 참고 (p.170)

 

• 스위치를 누르는 횟수의 모든 조합을 열거하면 무한할 것이다.
• 12시간 지나면 제자리로 돌아온다는 점을 이용해 유한하게 한정시키기
• 각 스위치를 누르는 횟수는 0에서 3번 사이이므로 전체 경우의 수는 $4^{10}=1,048,576$개
• 문제의 조건을 문자열로 표현하는 방법도 익히자

 

3.

import java.util.Scanner;

public class CLOCKSYNC {
    static final int INF = 9999, SWITCHES = 10, CLOCKS = 16;
    static final String linked[] = {
    	"xxx.............",
        "...x...x.x.x....",
        "....x.....x...xx",
        "x...xxxx........",
        "......xxx.x.x...",
        "x.x...........xx",
        "...x..........xx",
        "....xx.x......xx",
        ".xxxxx..........",
        "...xxx...x...x.." };
    static int[] clocks = new int[CLOCKS];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();

        for (int i = 0; i < c; i++) {
            for (int j = 0; j < CLOCKS; j++) {
                clocks[j] = sc.nextInt();
            }
            int answer = solve(clocks, 0);
            System.out.println(answer == INF ? -1 : answer);
        }

        sc.close();
    }

    static int solve(int[] clocks, int number) {
        if (number == SWITCHES) {
            return isAnswer(clocks) ? 0 : INF;
        }

        int ret = INF;
        for (int i = 0; i < 4; i++) {
            ret = Math.min(ret, i + solve(clocks, number + 1));
            pressButton(clocks, number);
        }
        return ret;
    }

    static void pressButton(int[] clocks, int number) {
        for (int i = 0; i < CLOCKS; i++) {
            if (linked[number].charAt(i) == 'x') {
                clocks[i] += 3;
                if (clocks[i] == 15)
                    clocks[i] = 3;
            }
        }
    }

    static boolean isAnswer(int[] clocks) {
        boolean flag = true;
        for (int i = 0; i < CLOCKS; i++) {
            if (clocks[i] != 12) {
                flag = false;
                break;
            }
        }
        return flag;
    }
}

 

 

4.

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (구종만)