[백준] 2661 좋은수열 java

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static int N;
    static int[] ans;
    static boolean isFirst = false;
    
    public static void backtracking(int[] arr, int depth) {
        if(depth > 1) {
            if(!isBadSequence(arr, depth)) return;
        }
        if(depth == N) {
            for(int i = 0; i < N; i++) {
                if(arr[i] > ans[i]) break;
                if(arr[i] < ans[i]) {
                    for(int j = 0; j < N; j++) {
                        ans[j] = arr[j];
                    }
                    isFirst = true;
                    break;
                }
            }
            return;
        }

        for(int i = 1; i <= 3; i++) {
            arr[depth] = i;
            backtracking(arr, depth+1);
            if(isFirst) return;
            arr[depth] = 0;
        }
    }

    public static boolean isBadSequence(int[] arr, int depth) {
        boolean flag = false;
        int pointer = 0;
        int cnt = depth / 2;
        //cnt번의 경우의 수만큼 돈다.
        for(int i = 1; i <= cnt; i++) {
            pointer = (depth-1)-i;
            int idx = depth-1;
            //pointer와 k부터 하나씩 비교한다.
            int k = i;
            while(k != 0) {
                flag = false;
                if(arr[idx] != arr[pointer]) {
                    flag = true;
                    break;
                }
                idx--;
                pointer--;
                k--;
            }
            if(!flag){
                return false;
            }
        }
        return flag;
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        ans = new int[N];
        Arrays.fill(ans, 4);
    }

    public static void main(String[] args) throws IOException{
        input();
        if(N == 1) {
            System.out.println(1);
        }
        else {
            int[] startArr = new int[N];
            Arrays.fill(startArr, 0);
            backtracking(startArr, 0);
            StringBuilder sb = new StringBuilder();
            for(int a : ans) {
                sb.append(a);
            }
            System.out.println(sb);
        }

    }
}

완전탐색 문제이고 백트래킹을 사용한 문제이다. N의 길이를 가진 좋은수열 중에서 최소값을 찾으면 된다.

 

문제 자체는 간단하다. 1부터 모든 경우의 수를 돌면서 좋은 수열인지 아닌지 판단해서 아니라면 가지치기 하고 좋은 수열이라면 계속해서 구해가면 된다. 그리고 처음으로 구해지는 좋은 수열이 곧 최소값인 좋은 수열이기 때문에 곧바로 함수를 종료해주면 된다.

 

문제의 핵심은 좋은 수열을 판단하는 과정이다.

 

우선 해당 수열에서 임의의 인접한 두 수열을 가질 수 있는 경우의 수는 수열의 길이 / 2 이다.

그렇기 때문에 arr.length / 2 만큼 돌면서 비교할 수열의 길이를 1씩 늘려가며 pointer 부분의 수열과 idx 부분의 수열을 하나씩 비교한다. 끝까지 비교해가며 완전히 동일한 경우는 나쁜 수열이기 때문에 바로 false를 리턴하고 아닌 경우는 다시 돌아가서 하나를 늘려 반복한다.

 

수열의 길이 / 2 만큼 반복하면서 비교했을 때 까지 나쁜 수열이 없으면 곧 좋은 수열이란 뜻으로 true를 리턴해주면 된다.