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;
                    }    
                }
            }
        }
    }
}


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

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