NERD2 책 내용 그대로 적었는데요

  • ANSY
    ANSY

    책에 나와있는 풀이를 그대로 적었습니다.
    예제 입/출력 했을때 답도 나왔구요
    근데 소스를 올리니 오답이라고 뜨네요.
    뭐가 문제일까요..

    소스코드입니다
    main만 제가 적었습니다.
    나머지는 책 내용 그대로구요.

    #include <iostream>
    #include <map>
    using namespace std;
    
    map<int, int> coords;
    
    bool isDominated(int x, int y) {
        map<int, int>::iterator it = coords.lower_bound(x);
    
        if(it == coords.end()) return false;
    
        return y < it->second;
    }
    
    void removeDominated(int x, int y) {
        map<int, int>::iterator it = coords.lower_bound(x);
    
        if(it == coords.begin()) return;
    
        --it;
    
        while(true) {
            if(it->second > y ) break;
    
            if(it == coords.begin()) {
                coords.erase(it);
                break;
            } else {
                map<int, int>::iterator jt = it;
                --jt;
                coords.erase(it);
                it = jt;
            }
        }
    }
    
    int registered(int x, int y) {
        if(isDominated(x, y)) return coords.size();
    
        removeDominated(x, y);
        coords[x] = y;
        return coords.size();
    }
    
    int main(){
    
        int caseNumber;
    
        cin >> caseNumber;
    
        for(int i = 0; i < caseNumber; i++){
            int n, sum = 0;
            cin >> n;
            for(int j = 0; j < n; j++) {
                int x, y;
                cin >> x >> y;
    
                sum += registered(x, y);
            }
            cout << sum << endl;
        }
    
        return 0;
    
    }
    

    10년 전
2개의 댓글이 있습니다.
  • Sharifa
    Sharifa

    caseNumber가 2 이상일 때, coords가 초기화되지 않아서 오답이 됩니다.
    예제의 경우 첫 번째 테스트 데이터의 최종 coords의 size는 3인데, 이것이 두 번째에 그대로 전해져서 3*5=15가 나와서 우연히 답이 된 겁니다.
    원래는 3+3+3+3+3이 아니라 1+2+3+4+5가 되어야 합니다.
    caseNumber for문 안에 적절한 곳에 coords.clear();만 추가하면 되겠군요.


    10년 전 link
  • ANSY
    ANSY

    아, 그러네요 ㅎㅎ
    고쳐서 맞았습니다!! 감사합니다~


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