[Algorithm] 백준/2661 :: 좋은수열

* 핵심

String에 += 사용 시 StringBuilder로 변환하여 Append 한 후에 toString 으로 변환 >> 많은 시간 소요

추가되는 문자열에 len/2 만큼만 반복하여 Backtracking 실행 >> 메모리 초과 에러 방지

* 문제

문제

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

* 소스 코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static int n;
    public static String res = "";
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(stk.nextToken());
        check("1");
    }
 
    public static void check(String s) {
        if (s.length() == n) {
            System.out.println(s);
            System.exit(0);
        } else {
            for (int i = 1; i <= 3; i++) {
                if (backtracking(s + i)) check(s+i);
            }
        }
    }
 
    public static boolean backtracking(String s) {
        int len = s.length();
        for (int i = 1; i <= len / 2; i++) {
            String front = s.substring(len - i * 2, len - i);
            String back = s.substring(len - i, len);
            if (front.equals(back)) return false;
        }
        return true;
    }
}