ALLERGY(알러지가 심한 친구들)에서 의미없는 if문의 유무로 결과가 달라집니다.

  • esoots
    esoots

    안녕하세요

    ALLERGY문제를 풀던 중에 질문이 있습니다.

    먼저 코드는 다음과 같구요

    #include <stdio.h>
    #include <string.h>
    
    void read();
    int getFriendIndex(char* name);
    void find(int friendIndex, long long staus, int select);
    
    int tcNum, friendsNum, foodNum;
    long long foods[50];
    long long friends[50];
    char names[50][11];
    long long full;
    int minNum = 987654321;
    int isOut;
    
    int main(){
        scanf("%d", &tcNum);
    
        for (int tc = 0; tc<tcNum; tc++){
            minNum = 987654321;
    
            memset(foods, 0, sizeof(long long)* 50);
            memset(friends, 0, sizeof(long long)* 50);
    
            read();
            isOut = 0;
    
            find(0, 0, 0);
    
            if (isOut){
                return -1;
            }
    
            printf("%d\n", minNum);
        }
    
        return 0;
    }
    
    void read(){
        int eatableNum;
        int friendIndex;
        char name[10];
    
        scanf("%d %d", &friendsNum, &foodNum);
    
        full = (1LL << friendsNum) - 1;
    
        for (int i = 0; i<friendsNum; i++){
            scanf("%s", names[i]);
        }
    
        for (int food = 0; food<foodNum; food++){
            scanf("%d", &eatableNum);
    
            for (int eatable = 0; eatable<eatableNum; eatable++){
                scanf("%s", name);
                friendIndex = getFriendIndex(name);
    
                foods[food] = (foods[food] | (1LL << friendIndex));
                friends[friendIndex] = (friends[friendIndex] | (1LL << food));
            }
        }
    }
    
    int getFriendIndex(char* name){
        for (int i = 0; i<friendsNum; i++){
            if (strcmp(names[i], name) == 0){
                return i;
            }
        }
    
        return -1;
    }
    
    void find(int friendIndex, long long status, int select){
        if (status == full){
            if (minNum > select){
                minNum = select;
            }
            return;
        }
    
        if (friendIndex == friendsNum){
            isOut = 1;
            return;
        }
    
        if (status & (1LL << friendIndex)){
            find(friendIndex + 1, status, select);
            return;
        }
    
        for (int i = 0; i<foodNum; i++){
            if (friends[friendIndex] & (1LL << i)){
                find(friendIndex + 1, status | foods[i], select + 1);
            }
        }
    }
    

    이렇게 실행하면 시간이 아슬아슬하게 (4초정도)로 통과가 되는데

    if (friendIndex == friendsNum){
        isOut = 1;
        return;
    }

    이 부분을 제거하고 올리면 시간초과가 뜹니다.
    책에서 나온 논리도 그렇고 코드에서도 모든 친구들을 한번씩 살펴봤는데도 못 먹는 친구가 있을 수가 없는데
    (게다가 if문이 없으면 더 빨라야 할 것 같은데)
    오히려 시간초과가 나서 이상하네요.. 혹시 도움 주실 수 있으신분 계신가요??

    3년 전
1개의 댓글이 있습니다.
  • 일루
    일루

    예기치 않게 컴파일러 최적화를 하신게 아닌가 싶습니다.

    minNum < select 면 무조건 리턴하는 부분을 추가하면 시간이 아슬아슬해지지 않을 것 같습니다.


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