백준 2661(JAVA)

문제

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

2661번: 좋은수열

풀이

1 2 3 밖에 존재하지 못하는 수열중, 가장 작은 좋은 수열을 구하면 된다.
즉, 나쁜수열이면 안된다..

가장 작은 숫자를 구하라 하였는데, 1 -> 2 -> 3 으로 탐색을 하면 자연스럽게 가장 작은 숫자가 나온다.

백트래킹 문제로 나쁜 수열이면 가지치기를 해서 경우를 많이 줄여 주면 간단하게 풀수있다.
즉, 재귀함수로 돌리다가 조건에 맞지않으면 그뒤의 가지들은 잘라버리고 다음 가지로 넘어간다. 만약 자른 가지가 엄청 큰 경우라면 엄청난 시간적 이득을 볼 수 있다.

문제는, 조건을 구하는 것이 꽤 까다로웠다. 문제는 30분정도 걸렸지만 28분정도를 조건을 생각하는데 썼다.

나는, N이 최대 80이므로, 큰 경우가 아니기에 브루트 포스를 통해 true, false를 반환했다.

즉, 길이가 1인녀석들 인접한거 모두 비교하고, 길이가 2인 녀석들 인접한거 모두 비교하고 ...

더 좋은 방법이 있을까 스택도 생각해보고, 삽질을 좀했다. 그런데 그냥 브루트 포스로 푼것이 맞았다.
N이 크지 않기에 가능하다.

코드

package training.backtracking;

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

public class Main2661 {
    static int N;
    static int[] result;

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

        recursive(0);

    }
    static void recursive(int m){
        if(m == N){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < N; i++){
                sb.append(result[i]);
            }
            System.out.println(sb.toString());
            System.exit(0);
        }

        for(int i = 1; i <= 3; i++){
            result[m] = i;
            if (!isValid(m)) { //가지치기
                result[m] = 0;
                continue;
            }

            recursive(m + 1);

            result[m] = 0;
        }
    }
    static boolean isValid(int m){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m + 1; i++){
            sb.append(result[i]);
        }

        String substr = sb.toString();

        // i는 탐색하는 문자열 길이
        for(int i = 1; i < substr.length() + 1; i++){
            if(i > (substr.length() / 2)) break;

            // j : pointer
            for(int j = 0; j < substr.length(); j++){
                if(j + 2 * i > substr.length()) break;
                String str1 = substr.substring(j, j + i);
                String str2 = substr.substring(j + i, j + 2 * i);
                if(str1.equals(str2)) return false;
            }

        }

        return true;
    }
}