[ BOJ ][JAVA][2661] 좋은수열

www.acmicpc.net/problem/2661

2661번: 좋은수열

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	7423	3776	2912	52.037%

문제

숫자 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들 사이에는 빈칸을 두지 않는다.

예제 입력 1

7

예제 출력 1

1213121

코드

/*
    좋은 수열인지, 나쁜 수열인지 분별해야 하는 코드를 구현해야 한다.
    길이가 n인 수열에서 인접하면서 동일한 수열이 있는 경우는 동일한 수열의 길이가 최소 1부터 최대 n/2인 경우 발생한다.
    따라서 가장 마지막에 집어넣은 수 기준으로
    마지막 1개와 그 앞의 1개의 수가 동일한지,
    마지막 2개와 그 앞의 2개의 수가 동일한지,
    마지막 3개와 그 앞의 3개의 수가 동일한지,
    ...
    마지막 n/2개와 그 앞의 n/2개의 수가 동일한지 비교를 해서 
    한번이라도 동일하다면 그 수열은 나쁜 수열이다.
    가장 첫 번째로 나오는 백트래킹 알고리즘의 결과가 결과중 가장 작은 수 이기 때문에
    첫번째를 바로 출력하면 된다.
*/
import java.io.*;
import java.util.*;

public class p2661 {
    static final int START = 1;
    static final int END = 3;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        bt("");
    }

    static void bt(String str) {
        if (str.length() == n) {
            System.out.println(str);
            System.exit(0);
            return;
        }

        for (int i = START; i <= END; i++) {
            if (promising(str + i)) {
                bt(str + i);
            }
        }
    }
    static boolean promising(String str) {
        int len = str.length();
        // ex. 1212가 들어올 경우
        // 한글자씩 비교했을 때는 유효하지만
        // 두글자씩 비교 했을 경우에는 12 12가 같으므로 유효하지 않다.
        for (int i = 1; i <= len / 2; i++) {
            String front_str = str.substring(str.length()-i-i, str.length()-i);
            String rear_str = str.substring(str.length()-i, str.length());
            if (front_str.equals(rear_str)) return false;
        }
        return true;
    }
}