좋은 수열 찾기

좋은 수열 (goodseq.cpp)

 

문제

---

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것 이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

33

32121323

123123213

다음은 좋은 수열의 예이다.

2

32

32123

1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램 을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수 열 1213121이다.

 

입력

---

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

 

출력

---

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내 는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

 

예제 입력

7

예제 출력

1213121

코드

//트리순회

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static int count = 0;
    public static boolean isFin = false;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int[] b;
        int c = 0;

        a = sc.nextInt();

        b = new int[a];

        printS(a,"");



    }

    public static void printS(int a, String x) {

        if(!isGood(x)) return;

        if(!isFin) {
            int len = x.length();
            if(a == 0){
                if(isGood(x)) {
                    System.out.println(x); isFin = true;
                }
                return;
            }
            if(len == 0 || !x.substring(len-1,len).equals("1")) {
                printS(a-1, x+1);
            }
            if(len == 0 || !x.substring(len-1,len).equals("2")) {
                printS(a-1, x+2);
            }
            if(len == 0 || !x.substring(len-1,len).equals("3")) {
                printS(a-1, x+3);
            }
        }

    }

    public static boolean isGood(String x) {

        int len = x.length();
        for(int i = 2 ; i <= len/2 ; i++) {

            for(int j = 0 ; j<= len-2*i; j++) {
                if(x.substring(j,j+i).equals(x.substring(j+i,j+2*i))) return false;
            }
        }

        return true;


    }

}