백준 2661번 좋은수열 :: 마이구미

이 글은 백준 알고리즘 문제 2661번 "좋은수열"을 풀이한다.

접근 방식은 백트래킹을 활용해 문제를 해결한다.

문제 링크는 다음과 같다.

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

DFS, BFS - http://mygumi.tistory.com/102

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열 1213121이다.

본인은 처음에 단순한 규칙이 존재할 것 같았다.

1213 가 계속해서 반복될 것 같았지만, 12131213 를 보면 그렇지도 않았다.

그래서 모든 경우를 탐색하는 방법을 택했다.

N자리까지 탐색할 때, 1 ~ N 자리를 탐색하는 과정에서 늘어나는 수열들 또한 좋은 수열이여야한다.

그렇기에 수열을 판단하면서 탐색이 이루어진다.

판단하는 기준은 1자리 ~ 길이/2 까지만 판단하면 된다.

예를 들어 다음과 같다.

1211 => 길이 4, 1자리 비교, 나쁜 수열

1212 => 길이 4, 1자리 비교, 좋은 수열
1212 => 길이 4, 2자리 비교, 나쁜 수열

123123 => 길이 6, 1자리 비교, 좋은 수열
123123 => 길이 6, 2자리 비교, 좋은 수열
123123 => 길이 6, 3자리 비교, 나쁜 수열

보다시피 비교할 수 있는 횟수와 기준은 길이의 절반이다.

구현 방법은 다양하다.

본인은 substring 메소드를 통해 두 문자열로 나누어서 비교하였다.

그리고 1 ~ 길이/2 자리까지 비교하기 위해 다음 코드로 구현했다.

public static boolean isSatisfy(String s) {
    int len = s.length();
    int loop = len / 2;
    int start = len - 1;
    int end = len;

    for (int i = 1; i <= loop; i++) {
        // i => 자릿수
        if (s.substring(start - i, end - i).equals(s.substring(start, end))) {
            return false;
        }
        start -= 1;
    }
    return true;
}

첫자리는 무조건 1이 나오기 때문에, 첫 탐색 기준 정점을 1만 해도 무방하다.

전체 코드는 다음과 같다.

static int n;
static boolean stop = false;
 
private void solve() {
    // http://mygumi.tistory.com/213
    n = sc.nextInt();
 
    dfs(1, "1");
}
 
public static void dfs(int len, String s) {
    if (stop) {
        return;
    }
 
    if (n == len) {
        stop = true;
        System.out.println(s);
    } else {
        for (int i = 1; i <= 3; i++) {
            if (isSatisfy(s + i)) {
                dfs(len + 1, s + i);
            }
        }
    }
    // backtracking
}
 
public static boolean isSatisfy(String s) {
    int len = s.length();
    int loop = len / 2;
    int start = len - 1;
    int end = len;
 
    for (int i = 1; i <= loop; i++) {
        if (s.substring(start - i, end - i).equals(s.substring(start, end))) {
            return false;
        }
        start -= 1;
    }
    return true;
}