글 읽기 - 반례를 모르겠습니다.

rosshjb 1년 전 0

어디서 틀렸다고 하는 것인지 모르겠네요.

조건을 저렇게 장황하게 나열하기까지 했는데 틀렸다고 나와서 도움 좀 구하고 싶습니다..

비교적 간단한 다른 풀이로는 풀 수 있었는데, 처음에 생각했던 방법대로 다시 해보고 싶어서요..

코드가 더럽기는 하지만..ㅠ

#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<pair<int, int>> persons;
    for (int i = 0; i < N; ++i) {
        pair<int, int> person;
        cin >> person.first >> person.second;
        persons.push_back(person);
    }
    vector<pair<int, int>> backup(persons);

    map<pair<int, int>, int> rank_map;
    int rank_count = 1;
    // persons 벡터에서 모든 사람이 지워질 때까지
    while (!persons.empty()) {
        // 가장 덩치가 큰 사람 찾기
        int biggest = 0;
        pair<int, int> biggest_person = persons[0];
        for (vector<pair<int, int>>::size_type i = 0; i < persons.size(); ++i) {
            if (persons[biggest].first < persons[i].first && persons[biggest].second < persons[i].second) {
                biggest = i;
                biggest_person = persons[biggest];
            }
        }
        // 덩치가 가장 큰 사람을 랭크 맵(<사람,등수>)에 저장하기
        rank_map.insert(make_pair(persons[biggest], rank_count));
        // 랭크 맵에 저장된 사람을 persons 벡터에서 제거하기
        persons.erase(persons.cbegin() + biggest);
        
        // 위에서 랭크 맵에 저장한 사람과 같은 덩치의 사람들 찾기
        int same_rank_count = 1;
        vector<pair<int, int>>::iterator it;
        while ((it = find_if(persons.begin(), persons.end(),
        [&](pair<int, int> p) {
            // 덩치가 같은 조건들
            return (
                (biggest_person.first > p.first && biggest_person.second == p.second)
            ||  (biggest_person.first == p.first && biggest_person.second > p.second)
            ||  (biggest_person.first < p.first && biggest_person.second == p.second)
            ||  (biggest_person.first == p.first && biggest_person.second < p.second)
            ||  (biggest_person.first < p.first && biggest_person.second > p.second)
            ||  (biggest_person.first > p.first && biggest_person.second < p.second)
            ||  (biggest_person.first == p.first && biggest_person.second == p.second)
            );
        })) != persons.end()) {
            // 덩치가 같은 사람들을 같은 등수로 랭크 맵에 저장하기
            rank_map.insert(make_pair(*it, rank_count));
            // 덩치가 같은 사람들도 persons 벡터에서 제거하기
            persons.erase(it);
            // 같은 덩치의 사람들 수 카운팅
            ++same_rank_count;
        }
        // 다음 번 랭크를 위한 계산
        rank_count += same_rank_count;
    }

    for (auto person : backup)
        cout << rank_map[person] << ' ';

    return 0;
}

zenith82114 1년 전 1

반례입니다.

4
6 10
4 2
6 4
10 6

출력: 1 4 1 1
정답: 1 4 2 1

rosshjb 1년 전 0

https://www.acmicpc.net/board/...

를 참고했습니다. 제가 문제를 잘못 읽었습니다. 생각했던 순위를 매기는 개념이 아니라 문제를 그대로 읽어야 하네요.

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

문제

문제

출처

ICPC

반례를 모르겠습니다.

rosshjb 1년 전 0

zenith82114 1년 전 1

rosshjb 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말