글 읽기 - (정답주의) 한 줄만 추가된 코드인데 걸린 시간이 너무 차이납니다.

dhtmdals130 1년 전 0

두번씩 테스트했습니다. while문 없는 코드가 오래 걸리는 겁니다.

풀고 나서 시간이 너무 많이 드는 것 같아 다른 분들의 코드를 참고했는데 다들 저 표시된 while문을 쓰시더라고요

그래서 저도 저 while문 하나만 딱 저기에 넣었는데 400ms 정도의 시간이 단축되었습니다.

근데 이유를 모르겠습니다... 저 코드에서 while문은 있거나 없거나 똑같은 거 아닌가요?

이게 합쳐진 for-if문 보다 while문 하나가 속도가 더 빨라서(물론 제 생각입니다) 그런 걸까요?

#include<iostream>
#include<vector>

int n,m,h;
bool Hline[31][11];
std::vector<std::pair<int,int>> pos;

bool check(){
    for(int i=1;i<=n;++i){
        int nowVline = i;
        for(int j=1;j<=h;++j){
            if(nowVline != n && Hline[j][nowVline]) nowVline++;
            else if(nowVline != 1 && Hline[j][nowVline-1]) nowVline--;
        }
        if(nowVline!=i) return false;
    }
    return true;
}

bool ladder(int lad, int idx){

    if(lad==0) return check();

    for(int i=idx;i<pos.size();++i){
        int h = pos[i].first;
        int v = pos[i].second;
        if(!Hline[h][v] && !Hline[h][v-1] && !Hline[h][v+1]){
            Hline[h][v] = true;
            if(ladder(lad-1, i+1)) return true;
            Hline[h][v] = false;
        }
    }

    return false;
}

int main(){

    std::cin >> n >> m >> h;

    for(int i=0;i<m;++i){
        int a, b;
        std::cin >> a >> b;
        Hline[a][b] = true;
    }

    // 문제의 코드 부분입니다

    for(int i=1;i<=n-1;++i)
        for(int j=1;j<=h;++j)
            if(!Hline[j][i] && !Hline[j][i-1] && !Hline[j][i+1]){
                pos.push_back({j,i});
                // 이 while문 한 줄만 추가했습니다
                while(j+2 < h && !Hline[j+2][i] && !Hline[j+2][i-1] && !Hline[j+2][i+1]) j++;
                //.
            }

    //.

    int ladnum=0;
    while(ladnum <= 3 && !ladder(ladnum,0)) ladnum++;
    if(ladnum > 3) std::cout << "-1";
    else std::cout << ladnum;
}

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

문제

문제

출처

ICPC

(정답주의) 한 줄만 추가된 코드인데 걸린 시간이 너무 차이납니다.

dhtmdals130 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말