백준 2661 - 좋은수열(Java)

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

문제

숫자 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

 

풀이

일단 빈 문자열을 선언 후,

백트래킹을 돌면서 1부터 3까지 추가해본다.

그렇게 만들어진 문자열을 check() 메서드에 던져서 가능한지 불가능한지를 확인한다.

문자열의 길이로 나누고 앞부분, 뒷부분을 비교해서 같은지를 보는 것.

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

public class BJ_2661_좋은수열 {
    static int N;
    static boolean exit = false;
    static String answer = "";
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        back(0);

    }
    public static void back(int cnt)
    {
        if(exit) return;
        if(cnt==N){
            System.out.println(answer);
            exit = true;
            return;
        }
        for(int i=1; i<4; i++)
        {
            answer+=i;
                if(check(answer))
                {
                    back(cnt+1);
                }
            answer = answer.substring(0,answer.length()-1);
        }

    }

    public static boolean check(String str) {
        for(int i = 1; i <= str.length() / 2; i++) {
            String front = str.substring(str.length() -i * 2, str.length() - i);
            String back = str.substring(str.length() - i, str.length());
            if(front.equals(back)) return false;
        }
        return true;
    }
}