좋은 수열 - 2661번

 

---

풀이 방법

DFS에서 조건을 걸어 백트래킹으로 풀이했다.

먼저 좋은 수열인지 아닌지 판단하는 check 함수를 작성해주었다. 

가장 작은 수를 나타내는 수열을 찾기 위해 DFS에서 1,2,3 순서대로 확인해 주었다. 

길이가 N과 같게 되면 find 를 true 로 해줘서 return 하는 것으로 구현했다.

 

내 코드

package com.company;

import java.io.*;


public class Main {
    static int N;
    static Boolean find = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        dfs("");

    }

    static void dfs(String num) {
        if(find)
            return;

        if (num.length() == N) {
            System.out.println(num);
            find = true;
            return;
        }

        if (check(num + "1")) {
            dfs(num + "1");
        }
        if (check(num + "2")) {
            dfs(num + "2");
        }
        if (check(num + "3"))
            dfs(num + "3");
    }

    static Boolean check(String num) {
        for (int i = 1; i <= num.length() / 2; i++) {
            for (int j = 0; j + 2 * i <= num.length(); j++) {
                String sub = num.substring(j, j + i);
                String temp = num.substring(j + i, j + 2 * i);
                if (temp.equals(sub)) {
                    return false;
                }
            }
        }

        return true;
    }
}