BOJ#2661 좋은수열

BOJ#2661 좋은수열

* 문제

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

* 풀이

- 수열의 시작은 무조건 1이다.

- 나쁜 수열인지 체크하는 알고리즘 세우기

- Backtracking 구성

1) 나쁜 수열 체크

2-1) 나쁜 수열인 경우 돌아가기

2-2) 좋은 수열인 경우

3-1) 길이를 다 채운 경우 -> 답을 return하고 모든 재귀함수를 종료한다.

3-2) 길이를 다 못채운 경우

4) 숫자 추가 (1~3 순서대로, 가장 작은 수를 만들어야 하기 때문에)

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%232661_GoodSequence/src

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

/**
 * BOJ#2661 좋은 수열
 * https://www.acmicpc.net/problem/2661
 */

public class Main {

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

        int N; // 수열의 길이
        String sequence = "1";

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        backtracking(N, 1, sequence);
    }

    static int backtracking(int N, int step, String sequence) {

        // 나쁜 수열인지 검사
        if (checkBadSequence(sequence)) {

            return -1;
        }

        // 길이가 N에 도달하였는지 체크
        if (step == N) {

            System.out.println(sequence);
            return 0;
        }

        for (int i = 1; i <= 3; i++) {

            sequence = sequence.concat(String.valueOf(i));
            if (backtracking(N, step + 1, sequence) == 0) {

                return 0;
            }
            sequence = sequence.substring(0, sequence.length() - 1);
        }

        return -1;
    }

    static boolean checkBadSequence(String sequence) {

        for (int i = 1; i <= sequence.length() / 2; i++) {

            for (int j = 0; j + 2 * i <= sequence.length(); j++) {

                if (sequence.substring(j, j + i).equals(sequence.substring(j + i, j + 2 * i))) {

                    return true;
                }
            }
        }

        return false;
    }
}