문제 ID : CLOCKSYNC, 난이도: 중

package main;
 
import java.util.ArrayList;
import java.util.Scanner;
 
public class MainClass {
    final static int INF = 9999;
    final static int SWITCHES = 10;
    final static int CLOCKS = 16;
    
    final static String[] str ={
            "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..",
    };
    
    public static boolean areAligned(int[] arr) {
        for(int b : arr) {
            if(b != 12) {
                return false;
            }
        }
        return true;
    }
    
    public static void push(int[] arr, int swtch) {
        int length = str[swtch].length();
        for(int i = 0; i < length; ++i) {
            if(str[swtch].charAt(i) == 'x') {
                arr[i] += 3;
                if(arr[i] == 15) {
                    arr[i] = 3;
                }
            }
        }
    }
    
    public static int solve(int[] arr, int swtch) {
        if(swtch == SWITCHES)
            return areAligned(arr) ? 0 : INF;
        
        int ret = INF;
        for(int i = 0; i < 4; ++i) {
            ret = Math.min(ret, i + solve(arr, swtch + 1));
            push(arr, swtch);
        }
        
        return ret;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int test = scanner.nextInt();
        ArrayList<int[]> list = new ArrayList<int[]>();
        
        int[] arr = null;
        for(int i = 0; i < test; ++i) {
            arr = new int[CLOCKS];
            for(int j  = 0; j < CLOCKS; ++j) {
                int input = scanner.nextInt();
                arr[j] = input;
            }
            list.add(arr);
        }
        
        for(int[] a : list) {
            int ret = solve(a, 0);
            System.out.println(ret);
        }
        
        scanner.close();
    }
}
 

위의 코드를 해석해 보면 아래와 같다.

 

i = 0

sw = 0

  sw = 1

   sw = 2

    sw = 3

     sw = 4

      sw = 5

       sw = 6

        sw = 7

         sw = 8

          sw = 9

           sw = 10

 

sw는 10일 때 areAlign 으로 체크하고 return false이면 12 12 12 9 9 9 12 12 12 9 12 12 12 9 12 12

 

0000000000 일때는 정렬이 되지 않는다는 뜻이다

 

그렇다면 다음 로직으로 

sw 가 10 일때 i = 1이 된다.

 

0000000001 일때 areAlign을 체크한다.

 

만약

0000000000

0000000001

0000000002

0000000003

모두가 false일 경우

 

00000000010 부터 다시 반복문을 실시한다.

 

00000000010

00000000011

00000000012

00000000013

 

위와 같은 행동을 반복해서 ret의 최소값을 알아낸다.

 

10중 반복문과 같은 일을 한다.

 

 

i를 계산하는 예를 들어 보면

0000000012 에서 areAlign = true; 라고 하면

for문의 i 는

sw 버튼을 i 번만큼 눌렀다는 뜻이고 INF값과 비교하여 작은 수가 return 되기 때문에

sw10번 버튼의 눌린 횟수를 return 해준다.

그 다음 reutrn한 i값과 sw가 9 일때 눌러준 i 값을 더해주면

총 버튼을 누른 값이 나온다.

 

재귀함수를 마지막 까지 반복하다 보면 ret값은 가장 최소값이 return 된다.