연습문제의 0-1문제입니다. 실행횟수를 줄였는데 시간초과가 뜹니다;;

  • nkj36
    nkj36

    0-1문제를 푸는 중에 실행횟수를 2천만번가량으로 줄였는데 시간초과가 뜹니다.
    입출력시간도 영향을 준다는 소리를 들어서 처음에 cin함수를 썼다가 scanf함수 fgets함수를 써봤는데 시간초과가 난걸보면 함수 실행자체의 시간때문인것같긴한데 제가 생각하기에는 2천만번 가량 계산이고 재귀함수가 그리 많은 코드를 갖은게 아니라 시간초과가 될것같지는 않습니다.
    혹시 문제점을 발견하시면 알려주시면 감사드립니다.

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    using namespace std;
    class zerone{
        public:
        vector<int> tem;
        int i1,j1;
        char in[1000001];
        zerone(){
            fgets(in,1000000,stdin);
            turn_num();
        }
        void turn_num(){
            for(int i=1;i<strlen(in);i++){
                if(in[i-1]!=in[i]){
                    tem.push_back(i);
                }
            }
        }
            int search(int i,int a,int b){
            if(b-a==1){
                return a;
            }
            if(tem[(a+b)/2]<=i){
                return search(i,tem.size()/2,tem.size());
            }
            else{
                return search(i,0,tem.size()/2);
            }
        }
            void zero_one(int i, int j){
            int min_num=search(i,0,tem.size());
            if(min_num<=j&&min_num>=i){
                printf("No");
            }
            else{
                printf("Yes");
            }
        }
    };
    int main() {
        int i,j,test;
        zerone *st=new zerone();
        scanf("%d",&test);
        while(test--){
            scanf("%d",&i);
            scanf("%d",&j);
            st->zero_one(i,j);
        }
        return 0;
    }
    

    이상입니다.


    6년 전
1개의 댓글이 있습니다.
  • seico75
    seico75

    시간초과 이전에 답은 잘 나오나요?
    제가 잘못이해한 것인지..
    수열에서 숫자가 바뀌는 인덱스를 tem 에 넣고 (turn_num)
    i,j를 받아서
    i 가 tem 내에 어디에 있는지를 찾고(search)
    그 어디가 i, j 밖에 있으면 No, 안에 있으면 yes로 하는 것 같은데...
    이런 논리와 문제에서 원하는 것 사이에 연관성을 모르겠습니다.

    제 생각에는

    사전작업을 O(N)에 해두면 (1의 수를 세어두는...) 이후의 i,j에 대해서는 O(1)으로 구할 수 있을 것 같습니다.


    6년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.