[Java] BaekJoon 2661. 좋은수열(골드4) (DFS) (백트래킹)

문제출처: https://www.acmicpc.net/problem/2661

2661번: 좋은수열

 

문제이해

 

목표

숫자 1, 2, 3으로만 이루어지는 수열이 있다.
임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다.
그렇지 않은 수열은 좋은 수열이다.
길이 N의 좋은 수열중 가장 작은 수를 구하자

 

풀이

 

1. 첫번째 자릿수부터 N번째 자릿수까지 DFS를 이용해서 수열을 구한다. 

   이때 배열에 오는 숫자의 우선순위 순서는 1, 2, 3 순이다.

 

2. 해당수열이 좋은 수열인지 확인하기 위해서 [1개 ~ (개수)/2] 만큼을 비교를 해야한다.

3. 비교를 할때 투포인터를 활용한다. 

4. 만약 투포인터를 이용해서 비교한 값 중 같은 개수가, 전체 비교 개수랑 같으면 나쁜 수열이므로 백트래킹한다. 

5. 아니라면 개수가 N이 될때까지 계속 DFS로 탐색한다.

  

소스코드

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

import static java.lang.System.in;

public class 좋은수열 {
    private static int N;
    private static int[] arr;
    private static int[] num123 = new int[]{1, 2, 3};
    private static boolean answerCheck;
    private static  StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        N = Integer.parseInt(br.readLine());
        answerCheck = false;
        arr = new int[N];

        getGoodSeq(0);
        // 정답출력
        sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(arr[i]);
        }
        System.out.println(sb);
    }

    private static void getGoodSeq(int count) {
        if (count == N) {
            answerCheck = true;
            return;
        }

        int compCount = (count + 1) / 2; // 몇 개씩 비교

        nextNum: for (int num = 0; num < 3; num++) { // 1,2,3 순서로 우선순위
            if(answerCheck){
                return;
            }
            arr[count] = num123[num];
            for (int i = 1; i <= compCount; i++) { // 몇개씩 비교할 건지
                int pointer1 = count; // 5
                int pointer2 = count - i; // 2
                int samCount = 0;
                for (int j = 0; j < i; j++) { // 투 포인터 개수만큼 비교
                    if(arr[pointer1--] == arr[pointer2--]){
                        samCount++;
                    }
                }
                if(samCount == i){ // 같은 개수가 비교 개수랑 같으면 나쁜 수열
                    continue nextNum;
                }
            }
            // 다음으로
            getGoodSeq(count + 1);
        }
    }
}