BOJ -2661

1. 문제

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

2. 풀이

문제의 이름은 좋은 수열인데 개인적인 생각으로는 문제는 나쁜문제..
수열의 경우 1, 2, 3중 하나가 들어가게 되고 임의의 길이의 인접한 두 개의 부분 수열이 동일하다면 나쁜 수열로 판단하기에 부분 수열을 나타내기 위해 substring을 사용하였다.

알고리즘을 완성하고 예제를 넣어보니 답이 잘 나오기에 제출하였는데 numberformat 에러가 발생했다. 생각해보니 string의 수열을 int형태로 바꾸려다 보니 int범위를 초과하는 것이 당연한데 그것을 간과하고 int형태로 변환해버렸다.

그 후 알고리즘을 자세히 보니 첫번째로 만들어지는 좋은 수열이 최소값이 된다는 것을 알았고 그것만 출력해주면 되기에 나머지 부분의 수정은 간단하였다.

import java.util.*;
import java.io.*;

public class Main2661 {
    static int N;
    static String [] arr = {"1", "2", "3"};
    static long result;
    static void rec(int count, String seq){
        if(count == N){
            System.out.println(seq);
            System.exit(0);
            return;
        }
        if(seq.length() == 0){
            rec(count+1, arr[0]);
        }
        else {
            for (int i = 0; i < 3; i++) {
                if (seq.charAt(seq.length() - 1) != arr[i].charAt(0)) {
                    String next = seq+arr[i];
                    if(next.length() >= 4) {
                        boolean flag = true;
                        for (int j = 1; j <= next.length() / 2; j++) {
                            if (next.substring(next.length() - j * 2, next.length() - j).equals(next.substring(next.length() - j, next.length())))
                                flag = false;
                        }
                        if(flag)
                            rec(count + 1, next);
                    }
                    else{
                        rec(count + 1, next);
                    }
                }
            }
        }

    }
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        rec(0, "");
    }
}

3. 적용된 알고리즘

백트래킹