• 백준 2529번 부등호 :: 마이구미
    알고리즘 풀이/그래프 2017. 12. 30. 15:58
    반응형

    이 글은 백준 알고리즘 문제 2529번 "부등호" 를 풀이한다.

    정올 초등부에서 출제된 문제이다.

    본인은 백트래킹을 활용해서 문제를 해결했다.

    문제 링크 - https://www.acmicpc.net/problem/2529


    두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

      A =>  < < < > < < > < >

    부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

      3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

    이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

       5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

    여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최대값과 최소값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.


    문제는 각 부등호에 넣을 수 있는 수를 구하는 것이다.

    부등호에 성립하는 수를 구하면서, 각 숫자는 중복되지 않는다는 점을 기억해야한다.

    구해지는 수는 여러 개가 존재할 수 있는데, 그 중 최대값과 최소값을 구해야한다.


    조금 까다로울 수도 있으나, 모든 경우를 탐색한다면 쉽게 해결할 수 있다.

    k의 갯수가 최대 10 이기 때문에, 모든 경우를 탐색해도 시간초과 걱정은 없다.


    DFS 를 통해 탐색하고, 모든 경우를 위해 백트래킹을 활용한다.

    백트래킹은 간단히 다음과 같은 그림으로 나타낼 수 있다.


    백트래킹


    그 과정속에서 부등호에 대한 조건과 수가 중복 여부를 체크하면서 탐색해주면 된다.

    탐색하는 과정속에서 탐색된 수가 k + 1 개가 되면, 부등호에 맞는 수가 완성된 것이다.

    반대로 그렇지 않다면, 불완전한 수이기 때문에 걸러주면 된다.


    기본적인 백트래킹을 활용한 DFS 에서 탐색 조건만 추가된 것이다.

    자세한 건 어렵지 않게 코드를 통해 이해할 수 있을 것이다.


    관련 문제 - http://mygumi.tistory.com/191?category=689692

    Github - https://github.com/hotehrud/acmicpc/tree/master/graph


    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
    static boolean[] visited = new boolean[10];
    static ArrayList<String> list = new ArrayList<String>();
    static String[] input;
    static int k;
     
    private void solve() {
        k = sc.nextInt();
        input = sc.readLine().split(" ");
     
        for (int i = 0; i <= 9; i++) {
            visited[i] = true;
            dfs(i, 0, i + "");
        }
        System.out.println(list.get(list.size() - 1));
        System.out.println(list.get(0));
    }
     
    public static void dfs(int v, int cnt, String str) {
        if (cnt == k) {
            // success
            list.add(str);
        } else {
            for (int i = 0; i <= 9; i++) {
                if (!visited[i]) {
                    if (input[cnt].equals("<")) {
                        if (v >= i) {
                            continue;
                        }
                    } else {
                        if (v <= i) {
                            continue;
                        }
                    }
                    visited[i] = true;
                    dfs(i, cnt + 1, str + i);
                }
            }
        }
        // backtracking
        visited[v] = false;
    }
    cs


    반응형

    댓글 0

Designed by Tistory.