• 백준 2505번 두 번 뒤집기 :: 마이구미
    알고리즘 풀이/수학 2018. 2. 5. 18:55
    반응형

    이 글은 백준 알고리즘 문제 2505번 "두 번 뒤집기" 를 풀이한다.

    정올 출제 문제로써, 문제 이해를 통한 구현으로 해결할 수 있다.

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


    1부터 N까지의 숫자가 각 칸에 차례대로 들어있는 놀이판이 있다. 예를 들어 10 칸을 가진 놀이판의 초기 상태는 다음과 같다.  

    12345678910

    구간[i,j]는 놀이판의 왼쪽 i번째 칸부터 j번째칸 사이에 있는 모든 숫자를 말한다. 단 구간[i,j]에서 항상  라고 가정한다. 우리는 이 놀이판의 한 구간을 잡아서 그 구간을 완전히 뒤집을  수 있다. 만일 초기상태에서 구간[3,8]을 뒤집으면 놀이판은 다음과 같이 변한다.

    12876543910

    이어 이 상태에서 구간[1,5]를 다시 뒤집으면 놀이판은 다음과 같이 바뀐다. 

    67821543910

    여러분은 두 번 뒤집힌 놀이판의 상태를 입력으로 받아서 이를 다시 초기 상태로 돌리기 위해서 어떤 두 구간을 차례대로 뒤집어야 하는지를 계산해야 한다. 즉 여러분이 찾아낸 두 개의 구간대로 입력 놀이판을 차례대로 뒤집으면, 놀이판은 초기상태인 1, 2, 3, ...., N 으로 되돌아가야 한다.  

    단 어떤 경우에는 초기상태로 되돌릴 수 있는 두 구간이 여러 개 있을 수도 있는데, 그러한 경우에는 그 중 하나만 출력해도 된다. 구간[i,i]를 뒤집으면 아무런 변화가 없는데 이러한 것도 허용이 된다.


    본인은 항상 문제를 제대로 읽고 풀겠다는 다짐을 해도 잘 지켜지지 않는다. 

    그로인해, 이 문제를 엄청 헤맸다.

    이 문제는 다시 한번 문제를 꼼꼼하게 읽고, 이해해야하는 것을 상기시켜준다.


    문제의 중점은 다음과 같다.


    1 ~ N 까지 순차적으로 되돌아가기 위한 구간을 찾는다.

    문제의 이름은 "두 번 뒤집기", 말 그대로 2번이다. 

    즉, 무조건 2번을 뒤집는다.


    예를 들어, 다음과 같이 주어졌을 경우를 보자.

    0번, 1번, 2번 뒤집는 경우가 존재한다. (답은 항상 존재한다고 명시했기에, 3번 이상 뒤집는 경우는 없다.)


    1 2 3 4 5

    => 1 1

    => 1 1


    1 2 3 5 4

    => 1 1

    => 4 5


    문제 설명을 보다시피 아무런 변화가 없는 것도 허용했다.

    그로인해, 무조건 답은 두 구간을 출력해주어야한다.

    이 부분에서 많이 틀렸을 것이라 생각한다.


    문제를 이해했다면, 이제 어떻게 뒤집는 구간을 찾을 것인가?

    항상 답이 존재하는 경우만 주기 때문에, 간단하게 생각할 수 있다.


    1 ~ N 까지 순차적이기에, 각 배열의 인덱스의 값은 인덱스와 동일한 값이 온다는 것을 알 수 있다.

    1 ~ N 의 값이 배열의 어느 인덱스에 위치하는 지 찾은 후, 뒤집어주면 된다.

    그림을 통해 표현하면 다음과 같다.


    2505번 두 번 뒤집기


    위와 같이 순차적으로 찾아 뒤집는 경우와 함께 역순으로 찾아 뒤집는 경우도 고려해야한다.

    Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2008/2505.java


    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
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    static StringBuilder sb1 = new StringBuilder();
    static StringBuilder sb2 = new StringBuilder();
    private void solve() {
        int[] array = new int[10001];
        int n = sc.nextInt();
     
        for (int i = 1; i <= n; i++) {
            array[i] = sc.nextInt();
        }
     
        if (front(array, 1, n)) {
            return;
        } 
        back(array, n, 1);
    }
     
    public static boolean front(int[] origin, int target, int n) {
        int[] array = origin.clone();
        int cnt = 0;
        while (target != n) {
            for (int i = target; i <= n; i++) {
                if (target == array[target]) {
                    break;
                }
                if (array[i] == target) {
                    cnt++;
                    reverse(array, target, i);
                    sb1.append(target + " " + i + "\n");
                }
            }
            target++;
        }
     
        if (cnt == 1) {
            System.out.println("1 1");
            System.out.println(sb1.toString());
            return true;
        } else if (cnt == 2) {
            System.out.println(sb1.toString());
            return true;
        } else {
            return false;
        }
    }
     
    public static boolean back(int[] origin, int target, int n) {
        int[] array = origin.clone();
        int cnt = 0;
        while (target != n) {
            for (int i = target; i >= n; i--) {
                if (target == array[target]) {
                    break;
                }
                if (array[i] == target) {
                    cnt++;
                    reverse(array, i, target);
                    sb2.append(i + " " + target + "\n");
                }
            }
            target--;
        }
     
        if (cnt == 1) {
            System.out.println("1 1");
            System.out.println(sb2.toString());
            return true;
        } else if (cnt == 2) {
            System.out.println(sb2.toString());
            return true;
        } else {
            System.out.println("1 1");
            System.out.println("1 1");
            return false;
        }
    }
     
    public static void reverse(int[] array, int s, int e) {
        int n = (int) Math.ceil((e - s) / 2.0);
        for (int i = 0; i < n; i++) {
            int temp = array[s + i];
            array[s + i] = array[e - i];
            array[e - i] = temp;
        }
    }
    cs


    반응형

    댓글

Designed by Tistory.