chapter06 : 시계 맞추기

문제

그림과 같이 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

 

문제회고

6장 마지막 문제.. 어느것하나 만만한게 없는 종만북...

중요한 포인트는 시간이 0 ~ 3을 주기로 반복된다는 것이다.
[3, 6, 9, 12], 3, 6, 9,....
주어진 스위치는 총 10개 이므로 시간복잡도를 생각해보면 4^10이다. 1억이 안되므로 완탐으로 돌려도 문제없다.

주의할점은 INF값에 Integer.MAX_VALUE를 넣으면 안된다는 것이다. max값을 넣게 되면 저기서 cnt값이 더해지면 overflow가 발생하여 음수로 바뀌어 버리고, 음수값이 답이되어버리기 때문이다.

코드

import java.util.*;
import java.io.*;  
import java.math.*;
public class Main {  
  
  static final int[][] LINKED = { 
    { 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 }
  };
  static final int SWTCH = 10; 
  static final int INF   = 987654321;
  static int[] clocks;
  
  
  // 1. 시계는 12시간이 지나면 제자리로 돌아온다.
  // 2. 열 개의 스위치를 누르는 모든 경우의 수 : 4^10
  
  // 모두 12시인지 확인한다.
  static boolean allSwitched() {
    for ( int i = 0; i < 16; ++i ) 
      if ( clocks[i] != 12 ) return false;
    return true;
  }
  
  
  static int solve ( int swtch ) {
    
    // 기저사례 : 스위치를 모두 눌렀을 경우 
    if ( SWTCH == swtch ) {
      // 스위치가 모두 눌렸을 경우 : 0 값을, 아닌경우 : 무한대 값을 반환
      return allSwitched() ? 0 : INF; // INF 주의점 : Integer.MAX_VALUE를 쓰지 않도록한다. 숫자가 너머 가면 음수가 된다.
    }
    
    // 0 ~ 3번까지 모든 경우의 스위치를 눌러본다. 4는 다시 0번을 누른거나 다름없으므로 의미없다.
    int ret = INF;
    for ( int i = 0; i < 4; ++i ) {
      ret = Math.min( ret, i + solve( swtch + 1 ) );
      
      // 스위치를 켠다.
      int[] linked = LINKED[swtch];
      for ( int j = 0; j < linked.length; ++j ) {
        clocks[ linked[j] ] += 3;
        if ( clocks[ linked[j] ] > 12 ) clocks[ linked[j] ] = 3;
      }
      
    }
    return ret;
  }
  
  
  // main  
  public static void main( String[] args ) throws Exception {
    
    // Please Enter Your Code Here 
    BufferedWriter bw  = new BufferedWriter( new OutputStreamWriter( System.out ) );
    BufferedReader br  = new BufferedReader( new InputStreamReader( System.in ) );
    StringBuilder sb   = new StringBuilder();
    StringTokenizer st = null;
    
    
    int C = Integer.parseInt( br.readLine() );
    while ( C --> 0 ) {
      // 입력값 셋팅 및 초기화
      clocks = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
      int ret = solve( 0 );
      if ( ret == INF ) sb.append( -1 ).append( "\n" );
      else sb.append( ret ).append( "\n" );
      
    } 
    
    bw.write( sb.toString() );
    bw.flush();
    bw.close();
    br.close(); 
  }  
  
} 

 

문제

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

algospot.com :: CLOCKSYNC