BOJ 2661 - 좋은 수열

[jusung-c]

문제

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

---

아이디어

먼저 조건 없이 생각해보면 숫자 1, 2, 3 중에서 중복을 허용하여 N개를 순서있게 나열하는 백트래킹 문제이다.

이 문제의 조건은 나쁜 수열을 제외하고 좋은 수열 중 가장 작은 수를 출력하는 것이다.
길이가 N인 수열에서 임의의 길이의 인접하는 두 개의 동일한 수열이 있는 경우를 나쁜 수열이라고 한다.

백트래킹을 통해 방문하면서 check 함수를 통해 좋은 수열만 다음 탐색으로 넘어갈 수 있도록 해준다.
방문을 할때마다 마지막에 넣은 수를 기준으로 마지막 i개와 그 앞의 i개를 비교해줘서 같을 경우 나쁜 수열로 처리한다.

길이가 N인 수열에서 나쁜 수열의 크기는 1부터 최대 N/2가 될 수 있다.

---

풀다가 결국 다른 사람 풀이 봤다.. 왜 내가 이걸 문자열로 해서 쉽게쉽게 비교할 생각을 못했지.. 문제 이름이 좋은 수열이라서 수로만 처리하려고 했던 것 같다ㅜㅜ

---

구현

import java.io.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;

    public static void main(String[] args) throws IOException {
        input();

        rec_func("");

    }

    static void rec_func(String str) throws IOException {
        if (str.length() == N) {
            bw.write(str);
            bw.close();
            System.exit(0);

        } else {
            for (int i = 1; i <= 3; i++) {
                
                // str에 i를 추가하면 나쁜수열이 되는 지 check 
                if (check(str + i)) {
                    // 좋은 수열이면 다음 탐색으로 ㄱㄱ
                    rec_func(str + i);
                }
            }
        }
    }

    static boolean check(String str) {

        for (int i = 1; i <= str.length() / 2; i++) {
            // 마지막 i개
            String back = str.substring(str.length() - i, str.length());

            // back 앞의 i개
            String front = str.substring(str.length() - i - i, str.length() - i);

            // 비교
            if (front.equals(back)) {
                // 동일하면 나쁜 수열
                return false;
            }
        }

        return true;
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
    }
}

---