티스토리 뷰

카테고리 없음

[CLOCKSYNC] 시계 맞추기

작은 거인 2018. 2. 4. 19:39

문제 주소

https://algospot.com/judge/problem/read/CLOCKSYNC


예제 입력

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


깃허브 주소

import java.util.Scanner;

public class Main {
private static final int CNT_CLOCK = 16, CNT_BUTTON = 10, MIN = 9999;
// int[버튼][시계] (1= 해당 버튼이 시계를 )
private static int[][] button_clock = {
{1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1},
{1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0},
{1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1},
{0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}
};

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int loop = sc.nextInt();
int[] clockArray = new int[CNT_CLOCK];
int[] result = new int[loop];
int tmp;

while (loop-- > 0) {

for (int i = 0; i < CNT_CLOCK; i++) {
clockArray[i] = sc.nextInt();
}

tmp = solve(clockArray, 0);
// 크게 나온 값은 불가능하다 판단하고 -1을 반환
result[loop] = tmp >= MIN ? -1 : tmp;

}

for (int i = result.length - 1; i >= 0; i--) {
System.out.println(result[i]);
}

}

// 모든 시계가 12시이 판별하는 메소드
private static boolean isAllClock12(int[] clockArray) {

for (int i = 0; i < CNT_CLOCK; i++) {
if (clockArray[i] != 12) {
return false;
}
}

return true;
}

private static void clickButton(int[] clockArray, int button) {

for (int clock = 0; clock < CNT_CLOCK; clock++) {
if (button_clock[button][clock] == 1) {
clockArray[clock] += 3;
if (clockArray[clock] == 15) {
clockArray[clock] = 3;
} // end of if
} // end of if
} // end of for

}

private static int solve(int[] clockArray, int button) {

// 0~9번 버튼에 대해 각각 times번 눌렀을 때, 12시인지 확인.
// 재귀 함수에 대해 헷갈렸던 부분.
// 4^10 완전 탐색을 하므로 10중 for문을 돌린다고 생각하면 좀 더 이해하기 쉽다.
if (button == CNT_BUTTON) {
return isAllClock12(clockArray) ? 0 : MIN;
}
int min = MIN;
// 아래 for문을 재귀 함수로 10중 for문을 만든다고 생각하면 된다.
// clickButton을 재귀 밑에 둠으로써 0번 눌렀을 때도 확인할 수 있으며,
// times가 3일때도 한 번 더 눌러 원상태로 만들어 다음 재귀 함수를 돌린다.
for (int times = 0; times < 4; times++) {
min = Math.min(min, times + solve(clockArray, button + 1));
clickButton(clockArray, button);
}
return min;
}

}

자바로 알고리즘 문제풀이를 준비하는 목적으로 '알고리즘 문제 해결 전략'을 분석하여 공부하고 있다. 추후 잊어버리지 않도록 정리한다.

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함