자물쇠( BOJ 2478 )

문제 : https://www.acmicpc.net/problem/2478

2478번: 자물쇠

 

문제 파악하기

주어진 수열을 만들기 위해 필요한 k-왼쪽밀기와 (p, q)-구간뒤집기 작업을 구하는 문제입니다. 모든 자물쇠는 [ k-왼쪽밀기 > (p, q)-구간뒤집기 > k-왼쪽밀기 ] 순서로 작업이 이루어지기 때문에, 우리는 반대로 [ k-오른쪽밀기 > (p, q)-구간뒤집기 > k-오른쪽밀기 ] 순서로 작업을 하여 정렬된 수열의 상태(1, 2, 3, ... , n)를 만들면 됩니다.

 

문제 해결하기

문제를 해결하기 위해서는 어느 구간에서 뒤집기가 일어났는지 파악하면 됩니다. 그럼 뒤집기가 일어난 구간은 어떻게 찾을 수 있을까요? 바로, 역순으로 정렬된 구간을 찾으면 됩니다. 정렬된 수열에서 뒤집기 작업을 한 경우에는 역순으로 정렬된 형태로 수열이 변하며, 우리는 역순으로 정렬된 구간을 찾아서 뒤집기 작업을 하면 됩니다. 다만, 역순으로 정렬된 구간을 찾을 때에 순진하게 첫 번째 숫자부터 차례대로 확인하면 안됩니다. 예를 들어, 다음과 같은 수열이 있다고 가정해봅시다.

 

6  5  4  3  9  10  1  2  8  7

 

위의 수열의 경우, 역순으로 정렬된 구간은 [ 8 7 6 5 4 3 ]까지 입니다. 하지만 왼쪽밀기 연산 때문에 인덱스 순서대로 역순으로 정렬되지 않습니다. 그렇기 때문에, 수열에서 모든 경우의 수를 확인해야 합니다.

 

이렇게 역순으로 정렬된 구간을 찾았다면 나머지 할 일은 적절하게 k-오른쪽밀기를 적용하면 됩니다. 여기서 말하는 적절하다는 의미는 뒤집을 구간이 항상 연속된 순서로 되어있으며, 뒤집기 연산이 일어난 후에 1의 위치가 첫 번째에 위치하지 않는 상황을 의미합니다. 수열을 하나씩 밀어보면서 적절한 k-오른쪽밀기 작업이 완료되면, 마지막으로 1의 위치를 찾아서 k-오른쪽밀기를 작업하면 됩니다.

 

다만, 모든 수열의 값이 역순으로 되어있다면 별도로 작업해야 합니다. 1의 위치가 n번째에 위치하지 않도록 k-오른쪽 밀기를 작업한 다음, 전체 수열을 뒤집고, 마지막으로 1의 위치를 찾으면 됩니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#define NMAX 500*2+1
 
int origin[NMAX], convert[NMAX];
 
int n;
int l, r;
int t, tmp_cnt, cnt;
 
void k_push() {
    for(int i=0;i<n;i++) origin[i] = convert[i];
 
    for(int i=0;i<n;i++) convert[(i+1)%n] = origin[i];
}
 
void pq_flip(int p, int q) {
    for(int i=0;i<n;i++) origin[i] = convert[i];
 
    for(int i=0;i<p;i++) convert[i] = origin[i];
    for(int i=p,j=q;i<=j;i++,j--) {
        convert[i] = origin[j];
        convert[j] = origin[i];
    }
}
 
int main() {
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        scanf("%d", &origin[i]);
        convert[i] = origin[i] = origin[i]-1;
    }
 
    for(int i=0;i<n;i++) {
        t = convert[i];
        tmp_cnt = 0;
        for(int j=(i+1)%n;j!=i;j=(j+1)%n) {
            if((t-1 + n)%n != convert[j]) break;
            tmp_cnt++;
            t = (t-1 + n)%n;
        }
 
        if(cnt < tmp_cnt) {
            cnt = tmp_cnt;
            l = i; r = (i+cnt)%n;
        }
    }
 
    // 해결방법
    // 1. 뒤집힌 구간 찾기 (뒤집히면 정렬되어있지 않음)
    // 2. 항상 맨 뒤쪽에서 뒤집기
    // 3. 뒤집은 후 1의 위치 찾기
 
    if(r-l+1 == n) {
        int p1, p2;
 
        // 1. 마지막 왼쪽밀기 (뒤집힌 구간 찾기)
        p1 = 0;
        do {
            k_push();
            p1++;
        }while(convert[n-1]==0);
 
        // 2. 구간 뒤집기 (항상 맨 끝에서 뒤집기)
        pq_flip(0, n-1);
 
        // 3. 첫 왼쪽밀기 (1의 위치 찾기)
        for(p2=0;convert[p2]!=0;p2++);
 
        printf("%d\n", n-p2);
        printf("%d %d\n", 1, n);
        printf("%d", p1);
    }
 
    else {
        int p1, p2;
 
        // 1. 마지막 왼쪽밀기 (뒤집힌 구간 찾기)
        for(p1=1;p1<n;p1++) {
            k_push();
            l = (l+1)%n; r = (r+1)%n;
 
            if(l>r) continue;
            else if((l==0 and !convert[r]) or !convert[0]) continue;
            else break;
        }
 
        // 2. 구간 뒤집기
        pq_flip(l, r);
 
        // 3. 첫 왼쪽밀기 (1의 위치 찾기)
        for(p2=0;convert[p2]!=0;p2++);
 
        printf("%d\n", n-p2);
        printf("%d %d\n", l+1, r+1);
        printf("%d", p1);
    }
}
 
/*
10
4 3 2 1 10 9 8 7 6 5
 
12
12 11 10 9 8 7 6 5 4 3 2 1
*/

후기

역순으로 정렬된 부분이 수열의 앞부분(0번 인덱스)으로 넘어갈 수 있다는 걸 미처 생각하지 못해 답답했던 문제입니다. 하지만, 스페셜 저지 문제이기 때문에 내가 설계한 방법대로 문제를 해결할 수 있다는 점이 매력적인 문제입니다.