• 백준 2661번 좋은수열 :: 마이구미
    알고리즘 풀이/그래프 2017. 9. 9. 21:49
    반응형

    이 글은 백준 알고리즘 문제 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만 해도 무방하다.

    전체 코드는 다음과 같다.


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    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;
    }
    cs


    반응형

    댓글

Designed by Tistory.