1. 주어진 보드판을 연속한 수열의 집합으로 생각(연속한 수열의 정의는 인접한 원소 간의 차가 전부 1인 경우를 의미). 예를 들어 문제에서 주어진 6 7 8 2 1 5 4 3 9 10은 (6~8), (2~1), (5~3), (9~10)이라는 4개의 수열의 집합으로 생각함

2. 보드판을 뒤집을 때 원래대로 복구를 하려면 각각의 수열은 수열 전체가 뒤집어지거나 수열 전체가 뒤집어지지 않아야함. 예를 들어 (6~8), (2~1), (5~3), (9~10)이 있을 때 (6~8) 전체를 뒤집는 것은 답이 될 수 있지만 7, 8만 뒤집는다거나 6, 7만 뒤집으면 절대 답이 될 수 없음

3. for문을 4번 돌려 답을 구함. 이 때 뒤집지 않는 경우도 예외처리로 고려를 했으며 주어진 보드판은 많아봐야 10개 이내의 수열의 집합이기 때문에 시간초과또한 걱정하지 않아도됨

위와 같은 아이디어로 풀었는데 틀렸다고 나오네요. 2번 과정이 잘못된 것인지 코딩에서 실수가 있었는지는 모르겠지만 코드를 아예 새로 짜기까지 했는데 계속 틀려요ㅠㅠ 도와주세요

/////코드 1

#include <stdio.h>
int abs(int x){
    if(x > 0)
        return x;
    return -x;
}
bool isalreadysorted(int arr[], int N){
    for(int i = 1; i <= N; i++){
        if(arr[i] != i)
            return false;
    }
    return true;
}
int main(void){
    int N;
    int num[10003];
    int num2[10003];
    int num3[10003];
    scanf("%d", &N);
    for(int i = 1; i <= N; i++){
        scanf("%d", &num[i]);
        num2[i] = num[i];
    }
    if(isalreadysorted(num, N)){ // 이미 정렬되어 있을 경우
        printf("1 1\n1 1");
        return 0;
    }
    int flip_l[10] = {0, };
    int flip_r[10] = {0, };
    //// 첫 번째 뒤집기
    int flipidx = 0;
    flip_l[flipidx] = 1;
    for(int i = 2; i <= N; i++){
        if( abs(num[i-1]-num[i]) != 1){ // 연속하지 않게 될 경우
            flip_r[flipidx++] = i - 1;
            flip_l[flipidx] = i;
        }
    }
    flip_r[flipidx++] = N;
    for(int i1 = 0; i1 < flipidx; i1++){
        for(int i2 = i1; i2 < flipidx; i2++){
            for(int i = flip_l[i1]; i <= flip_r[i2]; i++)
                num2[i] = num[ flip_l[i1] + (flip_r[i2] - i)]; // 첫 번째 flip 완료
            if(isalreadysorted(num2, N)){
                printf("%d %d\n1 1", flip_l[i1], flip_r[i2]);
                return 0;
            }
            int firstflip_1 = flip_l[i1];
            int firstflip_2 = flip_r[i2];
            flipidx = 0;
            flip_l[flipidx] = 1;
            for(int i = 2; i <= N; i++){
                if( abs(num2[i-1]-num2[i]) != 1){ // 연속하지 않게 될 경우
                    flip_r[flipidx++] = i - 1;
                    flip_l[flipidx] = i;
                }
            }
            flip_r[flipidx++] = N;
            for(int j1 = 0; j1 < flipidx; j1++){
                for(int j2 = j1; j2 < flipidx; j2++){
                    for(int i = 1; i <= N; i++)
                        num3[i] = num2[i];
                    for(int i = flip_l[j1]; i <= flip_r[j2]; i++)
                        num3[i] = num2[flip_l[j1] + (flip_r[j2] - i)]; // 두 번쨰 flip 완료
                    if(isalreadysorted(num3, N)){
                        printf("%d %d\n%d %d", firstflip_1, firstflip_2, flip_l[j1], flip_r[j2]);
                        return 0;
                    }    
                }
            }
        }
    }
}


다른 방법으로 아예 새로 다시 짜서 통과했긴한데 여전히 뭐가 문제인지는 모르겠네요ㅎㅎ;

안녕하세요.

엄청 오래전 글이지만 고민하시는 분들이 있을꺼 같아서 답변을 답니다.


2번 과정에서 다음과 같은 반례가 있을 것 같습니다.


8

1 2 5 6 3 4 7 8


말씀하신 알고리즘에서는 (1 2) (5 6) (3 4) (7 8)로 구간을 나누는데

실제 정답을 구하기 위해서는 (6 3 4)를 뒤집고 (5 4 3)을 뒤집어야 합니다.

와.. 코드를 다시 보니 짠 저 자신도 다시 읽기 싫어지는 코드인데 분석해주셔서 감사합니다!

댓글을 작성하려면 로그인해야 합니다.