BLOCKGAME문제 관련 질문입니다.

  • canuyes
    canuyes

    안녕하세요. 현재 BLOCKGAME문제를 풀고 있습니다.
    JM book을 참고하여 풀고 있는데 계속 TLE가 떠서 질문 올립니다.
    (아이디어는 모두 JM book과 동일함을 미리 밝힙니다.)

    제 코드는 이러합니다.

    #include<iostream>
    #include<cstring>
    #include<vector>
    
    #define TWO_25 33554432
    #define DEFAULT 0
    #define LOSE 1
    #define WIN 2
    
    using namespace std;
    
    char cache[TWO_25],answer[3][10]={"DUMMY","LOSING","WINNING"};
    vector<int> crit;
    
    void mk_crit(void){
        int i,b1=33,b2=3,b3=35,b4=67,b5=98,b6=97;
        for(i=0;i<20;i++,b1*=2,b3*=2,b4*=2,b5*=2,b6*=2){
            crit.push_back(b1);
            if(i%5!=4){
                crit.push_back(b3);
                crit.push_back(b4);
                crit.push_back(b5);
                crit.push_back(b6);
        }}
        for(i=0;i<25;i++,b2*=2){if(i%5!=4){crit.push_back(b2);}}
        return;
    }
    
    int input(void){
        int i,temp,val=1,ret=0;
        char ch;
        for(i=0;i<25;i++){
            cin>>ch;
            temp=(ch=='#')? 1:0;
            ret+=(val*temp);
            val*=2;
        }
        return ret;
    }
    
    char canWin(int state){
        char &ret=cache[state];
        if(ret==DEFAULT){
            ret=LOSE;
            for(int i=0;i<crit.size();i++){
                if((state&crit[i])==0){
                    if(canWin(state|crit[i])==LOSE){
                        ret=WIN;
                        break;
                    }
                }
            }
        }
        return ret;
    }
    
    int main(void){
        int T;
        cin>>T;
        mk_crit();
        while(T--){
            memset(cache,DEFAULT,sizeof(char)*TWO_25);
            cout<<answer[canWin(input())]<<endl;
        }
        return 0;
    }
    

    canWin 함수 부분과 input함수 부분은
    너무 간단하거나, 책과 동일하니 보지 않으셔도 됩니다.

    제가 궁금한것은 crit 부분입니다.
    JM book과 동일하게 모든 블록의 조합을 계산해냅니다.
    JM book의 코드에서도 moves의 size가 104,
    제 코드로 해도 moves의 size가 104가 나옵니다.

    결국 canWin 함수에서 순회 횟수도 동일하다는 이야기인데,
    왜 제 코드는 자꾸 시간 초과가 나는 것인가요?
    답변 기다립니다.


    10년 전
3개의 댓글이 있습니다.
  • Being
    Being

    cache가 매번 초기화될 필요가 있는지 생각해 보시기 바랍니다.


    10년 전 link
  • canuyes
    canuyes

    감사합니다 ㅠㅠ.
    매번 정말 큰 도움 받습니다!


    10년 전 link
  • rapguy
    rapguy

    저도 알고리즘책에 있는 그대로 제출했음에도 아무것도 없는 케이스에서 7초이상 걸려서 시간초과가 나왔습니다.

    하지만 canWin 함수에서 return 하면서 cache 에 값을 적어줄때 추가구현을 하니 pass 되었습니다.

    return 할때의 cache 값을 블록map으로 바꿔준 후에 그 블록을 90도, 180도, 270도, 미러링, 미러링된것을 90도, 180도 270도 맵을 회전시켜 해당 cache 값도 동일한 return 값으로 기록해주면

    return 하면서 cache 에 값을 1번 써줄것을 cache 8개에 써주는 효과로 시간이 빨라집니다.


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