[알고리즘] 백준 > #2661. 좋은수열

문제링크

백준 #2661. 좋은수열

풀이방법

일단 가장 작은 좋은수열을 구해야하기 때문에 1, 2, 3을 순서대롤 붙이는 dfs 방식을 생각했다. 그리고 수열의 부분수열이 나쁜수열이면 거기서 더 연장한 수열은 당연히 나쁜수열이기 때문에 부분수열을 이용해 가지치기를 했다! 좋은 수열인지 확인하는 부분은 한 인덱스를 기준으로 같은 길이를 잘라보며 확인했다. 끝!

코드

import java.util.*;

public class BOJ2661 {

    static int n;
    static String result = "";
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        searchMinGoodSequence("");
        System.out.print(result);
    }

    private static boolean searchMinGoodSequence(String sequence) {
        if (!isGoodSequence(sequence)) return false;
        else if (sequence.length() == n) {
            result = sequence;
            return true;
        }

        for (int i = 1; i <= 3; i++) {
            if (searchMinGoodSequence(sequence + Integer.toString(i))) return true;
        }

        return false;
    }

    private static boolean isGoodSequence(String sequence) {
        for (int i = 1; i < sequence.length(); i++) {
            int size = 1;

            while ((i - size >= 0) && (i + size - 1 < sequence.length())) {
                if (sequence.substring(i - size, i).equals(sequence.substring(i, i + size))) return false;
                size++;
            }
        }

        return true;
    }
}