[JAVA] 백준 2661- 좋은수열

https://www.acmicpc.net/problem/2661

 

 

 

 

문제를 보고나서, backtracking을 이용한 순열을 만들고, 순열을 하나 증가시킬때마다 이게 좋은수열인지 나쁜 수열인지 확인하는 과정으로 풀수 있겠구나 생각했다. 

그런데 문제는, TLE가 뜨냐 안뜨냐였는데, 문제조건에서 N은 최대 80이라고 했고, 숫자는 [1,2,3]만 허용한다했으니

최악의경우 3^80번 순열을 만들어야 하므로 당연히 시간초과가 날 것이라고 생각했다.

 

그래서 이건 백트래킹으로 풀수 없는 문제인가 싶어서 다른 방법을 생각해보았지만 도저히 떠오르지않았고,

순열을 만드는 숫자 후보 [1,2,3]을 작은 수부터 그리디하게 고르면 혹시 통과를 할수 있지 않을까? 생각해서 구현을 해보았는데

 

신기하게도 시간이 매우 적게 걸렸다.. 분명 최악의경우 3^80번을 돌면서 당연히 시간초과가 나지 않을까 생각했지만

내가 생각하기에 그리디 하게 어떤 수학적인 과정으로 최악의경우 3^80을 도는 경우가 아예 없겠구나.. 라고 생각했다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static int N;
    static ArrayList<Integer> list = new ArrayList<>(List.of(1,2,3));

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dfs(0, "");
    }

    static void dfs(int count, String seq){
        if(!valid(seq)) return;
        if(count == N){
            System.out.println(seq);
            System.exit(0);
            return;
        }
        for(int i = 0 ; i < 3 ; i++){
            dfs(count + 1, seq + list.get(i));
        }
    }

    static boolean valid(String seq){
        int length = 1;
        int size = seq.length();
        while(length * 2 <= size) {
            String sub = seq.substring(size - length, size);
            String target = seq.substring(size- length - length ,size-length);
            if(sub.equals(target)) return false;
            length++;
        }
        return true;
    }



}