백준 17359 자바 - 전구 길만 걷자 (boj 17359 java)

문제 : boj17359

 

 

  우선 브루트포스로 모든 경우를 본다면 10! 번을 봐야 한다. 사실 이건 360만번 정도로 충분히 가능한 횟수이다. 문제는 모든 경우를 이어본 후, 한땀한땀 바뀌는 부분을 구하려면 문자열의 길이가 최대 100 이므로 O(10!*100)이 필요하게 된다. 따라서 시간초과(사실 3억번정도에 중간에 추가 연산(세세한 덧셈 뺄셈 같은 것들)이 거의 없어 C나 C++이면 통과될것같긴하다 ㅋㅋ)가 날 것이다. 그럼 시간을 뺄 수 있는 아이디어를 생각해보자.

 

1. 각 묶음 내에서 바뀌는건 고정이다.

  즉, 어떻게 배치하게 되던지, 각 묶음 내에서 바뀌는건 어쨌든 고정적으로 바껴야 한다. 따라서 입력을 받으면서 내부에서 바뀌는걸 미리 세두자. 내 경우엔 confirmedCnt가 해당 역할을 한다.

 

 

2. 그럼 모든 문자의 맨 처음과 맨 끝만 보면 된다.

  '1'에서 내부에서 바뀌는걸 이미 세 두었으므로, 각 묶음의 맨 처음과 맨 끝만 보면 된다. 이 경우 O(10!) 이므로 문제없이 통과할 수 있다.

 

 

3. 예제 입력 1을 예시로 확인해보자.

  다음의 과정으로 확인하면 된다.

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    int n;
    int[][] arr;
    boolean[] v;
    int minCnt = 1001;

    private void recursion(int idx, int last, int cnt) {
        if (idx == n) {
            if (minCnt > cnt)
                minCnt = cnt;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (v[i]) continue;
            v[i] = true;
            recursion(idx+1, arr[i][1], cnt+(last != arr[i][0] ? 1 : 0));
            v[i] = false;
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        v = new boolean[n];
        arr = new int[n][2];
        int confirmedCnt = 0;
        for (int i = 0; i < n; i++) {
            String cur = br.readLine();
            for (int j = 1; j < cur.length(); j++) {
                if (cur.charAt(j-1) != cur.charAt(j))
                    confirmedCnt++;
            }
            arr[i][0] = cur.charAt(0)-'0';
            arr[i][1] = cur.charAt(cur.length()-1)-'0';
        }
        recursion(0, -1,-1);
        System.out.println(confirmedCnt + minCnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}