글 읽기 - 시간초과에서 벗어나고 싶습니다... 간절합니다..

nzzangyh 3년 전 0

미친놈처럼 3일동안 이문제만풀려고 10시간은 투자한거같은데,,

자괴감만 들고 있습니다...

구글링을 통해, 어떻게 풀면 시간초과안나는 모범답안 이겠구나라는 발상을 얻긴 했습니다만,

제 코드를 구제할수 없을까? 라는 욕심에 계속 매달렸는데 도저히 못하겠습니다..

제코드의 어떤 수정이 있어야지

c++언어로 시간초과를 벗어날 수 있을지 간절히 알고 싶습니다.

한분이 글로 올려주신, 밑에 내용이 제 코드에서 check_ladder, ladder라는 함수의 경우인데요,,

이것을 어떻게 어느시작점이 어느끝점으로 가는지에 대해 저장을할수있을지에 대한 아이디어도 생각이 안나서, 고견도 듣고싶습니다..

//시간 초과가 난다면 원인은 딱 하나입니다.

//사다리를 다 놓고 나서야 "i번 세로선의 결과가 i번이 나와야 한다"를 직접 시뮬레이션을 돌려서 확인하는 것은 매우 비효율적입니다.

//사다리를 하나 놓을 때마다 어느 시작점이 어느 끝점으로 가는지 저장해 두면 시뮬레이션을 안 돌리고 바로 확인할 수 있습니다.

#include <cstdio>
#include <vector>
#include <limits.h>
using namespace std;
int result_state = 0;
int result = INT_MAX;
int initial_result = 0;
int v[35][15] = {0,};
int ladder(int col, int width, int height){
    for(int i = 0; i<height; i++){
        if(v[i][col] == 1){
            col+=1;
        }
        else if(v[i][col] == 2){
            col -=1;
        }
    }
    
    return col;
}
bool check_ladder(int width, int height){
    int state = 0;
    for(int i = 0; i<width; i++){
        int result = ladder(i, width, height);
        if(result == i){
            state = 1;
        } else{
            state = 0;
            break;
        }
    }
    
    if(state == 1){
        result_state  = 1;
        return true;
    } else{
        return false;
    }
}

void make_ladder(int row, int col, int width, int height, int cnt){
    if(result_state)
        return;
    /*
    if(col+1<width){
        if(v[row][col+1])
            return;
    }*/
    //vector<vector<int>> v2 = v;
    if(!v[row][col]&&col+1<width&&!v[row][col+1]){
        v[row][col] = 1;
        v[row][col+1] = 2;
        cnt++;
        
        //이제 이부분에서 추가해야 하는 가로선 개수의 최솟값을 체크하는 함수를 실행시키면 됨.
        if(check_ladder(width, height)){
            // if(cnt < result){
            //printf("여기들오나?\n");
            result = cnt;
                v[row][col] = 0;
                v[row][col+1] = 0;
            return;
            // }
        }
    }
    
    
    if(cnt==3)
        return;
    
    for(int i = row; i<height; i++){
        
        if(i== row){
            //하 ,, 씨@발 여기 조건문이 이상했다.
            for(int j = col+2; j<width-1; j++){
                
                //여기 조건을 체크해줘야한다!!!!
                if(!v[i][j]) //사다리가 만들어져있지 않을때,
                {
                    make_ladder(i, j, width, height, cnt);
                    if(v[i][j] == 1 &&v[i][j+1] == 2){
                        v[i][j] = 0;
                        v[i][j+1] = 0;
                    }
                }
            }
        }
        
        else if(i != row)
        {
            for(int j = 0; j<width-1; j++){
                //여기 조건을 체크해줘야한다!!!
                if(!v[i][j]) //사다리가 만들어져있지 않을때,
                {
                    make_ladder(i, j, width, height, cnt);
                    if(v[i][j] == 1 &&v[i][j+1] == 2){
                        v[i][j] = 0;
                        v[i][j+1] = 0;
                    }
                }
            }
        }
    }

    return;
}
int main(int argc, const char * argv[]) {
    int N, M, H;
    scanf("%d %d %d", &N, &M, &H);
    //vector<vector<int>> v;
    
    //하,,여기서 행과열을 잘못만들어준거같다 ㄷㄷ;
//    for(int i = 0; i<H; i++){
//        vector<int> vv(N);
//        v.push_back(vv);
//    }
    
    for(int i = 0; i<M; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        v[a-1][b-1] =  1;
        v[a-1][b] = 2;
        //범위체크조심해야할듯 인덱스벗어날수도 있을것같은데.
    }
    
    initial_result = M;
    
     int cnt = 0;
    
    check_ladder(N, H);
    if(result_state == 1){
        printf("%d\n", cnt);
        return 0;
    }

    
  // make_ladder(0,0,N, H, cnt);
    for(int i = 0; i<H; i++){

        for(int j = 0; j<N-1; j++){

           if(!v[i][j])
            {
                make_ladder(i,j,N, H,  cnt);
                if(v[i][j] == 1 &&v[i][j+1] == 2){
                    v[i][j] = 0;
                    v[i][j+1] = 0;
                }
            }
        }
    }
    
    if(result_state == 0 || result > 3){
        printf("-1\n");
    }
    else{
    printf("%d\n", result);
    }
    return 0;
}

check_ladder 부분에서 state=0일때는 되자마자 return false; 바로 해버리는 건 어떨까요? 저 또한 비슷한 방식이었어서 말씀드리자면..
문제 테스트케이스 맞으시고, 9%에서 멈추신거면, 아마 2초에 간당간당 하실거 같고, 그거만 넘기시면 아마 통과하실거라고 생각들어요. 시간초과가 나기 쉬울수 밖에 없는 것이 1개때 놓았던 곳을 3개 놓을 때 또 다시 중복적으로 놓고 있어서 그렇더라구요.
다른 한가지는 저 같은 경우 왼쪽에 1, 오른쪽에 2로 하지 않았고, 그냥 사다리를 1로 본다음 j-1에 1이있으면, j입장에서 왼쪽에 연결 되어있으니까 j-1로 가고, j에 1이 있으면 오른쪽으로 가라는 식으로 했었어요. 별 차이가 없어보였지만 제가 처음에 짠 코드에서 1. a[i][j] =1; a[i][j+1]=2;로 구현했을 때와 2. a[i][j]=1;로만 놓고 if(a[i][j-1] == 1) j-=1; else if(a[i][j] == 1) j+=1; 로 했을때전자는 시간초과났고 후자는 간당간당하게 통과했습니다. 엄청 빠르게 하려면 뜯어 고쳐야하지만 최대한 안 고치는 선에서 말씀드립니다. 도움이 되셨다면 한번 실행해보세요~!

cesta123 3년 전 1

아 그리고 후자 방식으로 해보실거면, 처음에 초기화 부분에서 v[a-1][b] = 2;이거 빼시고 하셔야 합니다. 고칠 때 처음에 빼는거 깜빡하고 안됐어서 당황했었거든요

nzzangyh 3년 전 0

댓글 고맙습니다. 답변자님의 이 문제에 대한 채점현황을 보니, 저와같이 고생하셨다는 것이 느껴지네요,,,

나중에 말씀해주신 부분으로 꼭 참고해서 통과해보겠습니다.

내일 좋은결과있으시길!

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

문제

문제

출처

ICPC

시간초과에서 벗어나고 싶습니다... 간절합니다..

nzzangyh 3년 전 0

cesta123 3년 전 2

cesta123 3년 전 1

nzzangyh 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말