OLYMPICS 문제 질문드립니다.

  • xtozero
    xtozero

    OLYMPICS에 관해서 질문드리고 싶습니다.
    빼먹고 있는 부분이 있는지 계속 오답이 나와서 멘붕이네요.

    아래와 같은 방식으로 시도하였습니다.

    첫번째 경우
    1. 금메달을 남은 경기만큼 획득.
    2. 이미 금메달로 앞서고 있는 국가 수 * 경기 수 만큼 메달 개수를 줄이고 등수도 내림니다.
    3. 남은 메달을 골고루 분배 할 수 있는지 보고 분배할 수 없으면 가장 잘하고 있는 국가 순으로 메달을 주고 메달을 골고루 분배 가능하거나 다 줄때까지 반복하며 등수를 내림니다..

    두번째 경우
    1. 금메달을 남은 경기만큼 획득
    2. 이미 금메달로 앞서고 있거나 지고 있는 국가가 2국가 이상이면 현재 상태로 등수를 계산.
    3. 1국가 이상이면 은메달을 전부 줄 수 있다고 생각하고 동메달을 분배. 골고루 나눠 줄 수 없으면 한국가 한테 졌다고 판단하여 등수를 내림니다.
    4. 없으면 이미 은메달로 이기고 있는 국가를 세어 보고 2팀 이상이면 동메달 은메달을 그 팀들에게 줬다고 생각하고 등수를 계산
    5. 1팀 이상이면 은메달을 그팀에게 줬다고 생각하고 동메달을 분배 해봐서 분배 할 수 없으면 한팀에게 졌다고 판단합니다.
    6. 은메달로 이기고 있는 국가가 없으면 은메달을 골고루 나눠 줄 수있는지 봅니다.
    7. 은메달을 분배했는데 여유가 있으면 하나 적은 은메달 갯수로도 분배 가능한지 보고 가능하면 바로 등수를 정하고 불가능하면 현재 은메달의 개수가 같은 국가가 있는지 보고 없으면 아무 국가나 하나 정해서 그곳에 몰아주고 한팀에게 졌다고 판단하고 같은 국가가 있으면 동메달의 갯수가 많은지 보고 많으면 해당 국가에 은메달을 몰아줬다고 생각해서 국가 수만큼 등수를 올립니다.
    8. 정확히 분배되면 동메달로 분배 가능한지 보고 불가능 하면 은메달을 은메달, 동메달 갯수 순으로 정렬했을 때 가장 많은 한팀에 몰아 준다음 다시 동메달을 분배해봅니다.
    9. 모자라면 한팀을 골라서 몰아 준다음 다시 동메달을 분배해봅니다.

    두번째 경우는 다시짜는게 좋을 정도로 복잡하네요.
    아래는 마지막으로 제출한 코드입니다.

    #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Nation
{
public:
    int m_gold;
    int m_silver;
    int m_bronze;
    int m_total;

    int GetTotal( ) const { return m_total; }

    Nation( int gold, int silver, int bronze ) : m_gold( gold ),
        m_silver( silver ),
        m_bronze( bronze )
    {
        m_total = m_gold + m_silver + m_bronze;
    }

    Nation( const Nation& nation ) :
        m_gold( nation.m_gold ),
        m_silver( nation.m_silver ),
        m_bronze( nation.m_bronze ),
        m_total( nation.m_total )
    {

    }
};

void simulateBestRankWay1( const vector<Nation>& nations, const int remain  )
{
    for ( unsigned int i = 0; i < nations.size( ); ++i )
    {
        vector<int> greater;
        vector<pair<Nation, int>> lesser;

        int myTotalMedal = nations[i].GetTotal( ) + remain;

        for ( unsigned int j = 0; j < nations.size( ); ++j )
        {
            if ( i == j )
            {
                continue;
            }
            else if ( nations[j].GetTotal() > myTotalMedal )
            {
                greater.emplace_back( remain );
            }
            else
            {
                lesser.emplace_back( nations[j], min( max( myTotalMedal - nations[j].GetTotal( ), 0 ), remain ) );
            }
        }

        int remainMedal = remain * 2;
        unsigned int rank = 1;

        //이미 이기고 있는 국가 수만큼 remainMedal을 줄이고 rank를 늘린다.
        remainMedal -= greater.size( ) * remain;
        rank += greater.size( );

        int totalRemain = 0;
        if ( remainMedal > 0 )
        {
            for ( auto nation : lesser )
            {
                totalRemain += nation.second;
            }
        }

        //골고루 분배가 안돼면
        if ( remainMedal > totalRemain )
        {
            //가장 잘하고 있는 국가순으로 몰아준다.
            sort( lesser.begin( ), lesser.end( ), []( const pair<Nation, int>& lhs, const pair<Nation, int>& rhs ) -> int
            {
                return lhs.first.GetTotal() > rhs.first.GetTotal( );
            } );

            for ( auto nation : lesser )
            {
                if ( remainMedal <= totalRemain )
                {
                    break;
                }

                rank += 1;
                remainMedal -= remain;
                totalRemain -= nation.second;
            }
        }

        if ( i != 0 )
        {
            cout << ' ';
        }
        cout << rank;
    }

    cout << endl;
}

void simulateBestRankWay2( const vector<Nation>& nations, const int remain )
{
    for ( unsigned int i = 0; i < nations.size( ); ++i )
    {
        int greater = 0;
        vector<pair<Nation, int>> goldEqual;
        int lesser = 0;

        int myGold = nations[i].m_gold + remain;
        int mySilver = nations[i].m_silver;
        int myBronze = nations[i].m_bronze;

        int remainSilver = remain;
        int remainBronze = remain;

        int rank = 1;

        //우선 금메달부터 세 그룹으로 나눈다.
        for ( unsigned int j = 0; j < nations.size( ); ++j )
        {
            if ( i == j )
            {
                continue;
            }
            else if ( nations[j].m_gold > myGold )
            {
                ++greater;
            }
            else if ( nations[j].m_gold == myGold )
            {
                goldEqual.emplace_back( nations[j], min( max( mySilver - nations[j].m_silver, 0 ), remain ) );
            }
            else
            {
                ++lesser;
            }
        }

        //이미 이겨버린 국가 만큼 랭크를 더한다.
        rank += greater;

        //이미 내 앞에서 이미 이기거나 진 팀이 2팀 이상이면 더 이상 분배하지 않아도 된다.
        if ( greater + lesser >= 2 )
        {
            for ( auto nation : goldEqual )
            {
                if ( nation.first.m_silver > mySilver )
                {
                    rank += 1;
                }
                else if ( nation.first.m_silver == mySilver )
                {
                    if ( nation.first.m_bronze > myBronze )
                    {
                        rank += 1;
                    }
                }
            }
        }
        //한팀만 금메달로 이기거나 졌으면 은메달을 전부 줘버리고 동메달을 분배한다.
        else if( greater + lesser == 1 )
        {
            greater = 0;
            lesser = 0;

            for ( auto nation : goldEqual )
            {
                if ( nation.first.m_silver > mySilver )
                {
                    ++greater;
                }
                else if ( nation.first.m_silver < mySilver )
                {
                    ++lesser;
                }
                else
                {
                    remainBronze -= min( max( myBronze - nation.first.m_bronze, 0 ), remain );
                }
            }

            rank += greater;

            //은메달로 이기거나 진 국가가 없으면 동메달을 나눠줄 수 있는지 보고 나누지 못하면 한 팀에게 져야한다.
            if ( greater + lesser == 0 )
            {
                if ( remainBronze > 0 )
                {
                    rank += 1;
                }
            }
        }
        else //그것도 아니면 은메달도 분배해야한다.
        {
            greater = 0;
            lesser = 0;
            for ( auto nation : goldEqual )
            {
                if ( nation.first.m_silver > mySilver )
                {
                    ++greater;
                }
                else
                {
                    if ( nation.first.m_silver < mySilver )
                    {
                        ++lesser;
                    }
                    //은메달을 바로 분배해 본다.
                    remainSilver -= nation.second;
                }
            }

            rank += greater;

            // 이미 은메달로 이기고 있는 팀이 2이상 있었으면 은메달 동메달을 그팀들에게 주고
            if ( greater > 1 )
            {
                //남은 팀들의 동메달을 비교해본다.
                for ( auto nation : goldEqual )
                {
                    if ( nation.first.m_silver == mySilver )
                    {
                        if ( nation.first.m_bronze > myBronze )
                        {
                            rank += 1;
                        }
                    }
                }
            }
            else if( greater == 1 )
            {
                // 나눠 줄 은메달이 없는데 은메달이 원래 적었던 국가도 없다.
                if ( lesser == 0 )
                {
                    //동메달 분배 해봐야 한다.
                    greater = 0;
                    for ( auto nation : goldEqual )
                    {
                        if ( nation.first.m_silver == mySilver )
                        {
                            if ( nation.first.m_bronze > myBronze )
                            {
                                ++greater;
                            }
                            remainBronze -= min( max( myBronze - nation.first.m_bronze, 0 ), remain );
                        }
                    }

                    rank += greater;

                    if ( greater == 0 && remainBronze > 0 )
                    {
                        rank += 1;
                    }
                }
                else
                {
                    for ( auto nation : goldEqual )
                    {
                        if ( nation.first.m_silver == mySilver )
                        {
                            if ( nation.first.m_bronze > myBronze )
                            {
                                rank += 1;
                            }
                        }
                    }
                }
            }
            else
            {
                if ( remainSilver < 0 )
                {
                    //은메달 분배했는데 여유가 있다.
                    //내 은메달 보다 하나 적은 은메달로 분배가 가능한지 본다.
                    remainSilver = remain;
                    for ( auto nation : goldEqual )
                    {
                        remainSilver -= min( max( mySilver - 1 - nation.first.m_silver, 0 ), remain );
                    }

                    //나보다 하나 적은 은메달로 분배하기에는 많다.
                    if ( remainSilver > 0 )
                    {
                        remainSilver = remain;

                        sort( goldEqual.begin( ), goldEqual.end( ),
                            [mySilver, myBronze]( const pair<Nation, int>& lhs, const pair<Nation, int>& rhs )->int
                        {
                            return lhs.first.m_bronze  < rhs.first.m_bronze;
                        } );


                        int equal = 0;
                        int moreBronze = 0;

                        for ( auto nation : goldEqual )
                        {
                            if ( nation.first.m_silver == mySilver )
                            {
                                ++equal;
                                if ( nation.first.m_bronze > myBronze )
                                {
                                    ++moreBronze;
                                }
                            }

                            if ( nation.first.m_bronze <= myBronze )
                            {
                                remainSilver -= min( max( mySilver - nation.first.m_silver, 0 ), remain );
                            }
                            else
                            {
                                remainSilver -= min( max( mySilver - 1 - nation.first.m_silver, 0 ), remain );
                            }
                        }

                        if ( remainSilver > 0 )
                        {
                            if ( equal == 0 )
                            {
                                rank += 1;
                            }
                            else if ( moreBronze > 0 )
                            {
                                rank += moreBronze;
                            }
                        }
                    }
                    else
                    {
                        for ( auto nation : goldEqual )
                        {
                            if ( nation.first.m_silver > mySilver )
                            {
                                ++greater;
                            }
                            else if ( nation.first.m_silver == mySilver )
                            {
                                if ( nation.first.m_bronze > myBronze )
                                {
                                    ++greater;
                                }
                            }
                        }
                    }

                    remainSilver = 0;
                }
                else if ( remainSilver == 0 )
                {
                    //동메달 분배 해봐야 한다. 배분 가능한 동메달의 최대 양은 remain - nation.second이다.
                    //동메달이 딱 떨어지거나 넉넉하면 거기서 끝내면 되는데 딱 안떨어지면 더 봐야한다.
                    for ( auto nation : goldEqual )
                    {
                        remainBronze -= min( max( myBronze - nation.first.m_bronze, 0 ), remain - nation.second );
                    }

                    if ( remainBronze > 0 )
                    {
                        remainBronze = remain;
                        remainSilver = 1;
                    }
                }

                //은메달이 남았으면 한 팀 한테는 져야 한다.
                if ( remainSilver > 0 )
                {
                    rank += 1;
                    //져줘야 할 팀을 고른다음 동메달 분배 해봐야 한다.
                    lesser = 0;
                    greater = 0;

                    sort( goldEqual.begin( ), goldEqual.end( ), 
                        [mySilver,myBronze]( const pair<Nation, int>& lhs, const pair<Nation, int>& rhs )->int
                        {
                            if ( lhs.first.m_silver == rhs.first.m_silver )
                            {
                                return lhs.first.m_bronze  > rhs.first.m_bronze;
                            }
                            else
                            {
                                return  lhs.first.m_silver > rhs.first.m_silver;
                            }
                        }
                    );

                    //한팀에 몰빵한다.
                    goldEqual.begin( )->first.m_silver += remain;

                    for ( auto nation : goldEqual )
                    {
                        if ( nation.first.m_silver < mySilver )
                        {
                            ++lesser;
                        }
                        else if (nation.first.m_silver == mySilver)
                        {
                            //이미 동으로 앞서고 있는 국가의 수도 세줘야한다.
                            if ( nation.first.m_bronze > myBronze )
                            {
                                ++greater;
                            }
                            else
                            {
                                remainBronze -= min( max( myBronze - nation.first.m_bronze, 0 ), remain );
                            }
                        }
                    }

                    rank += greater;

                    if ( lesser == 0 && greater == 0 && remainBronze > 0 )
                    {
                        rank += 1;
                    }
                }
            }
        }

        if ( i != 0 )
        {
            cout << ' ';
        }
        cout << rank;
    }

    cout << endl;
}

int main( )
{
    unsigned int testCase = 0;

    cin >> testCase;

    for ( unsigned int i = 0; i < testCase; ++i )
    {
        unsigned int totalNations = 0;
        int remain = 0;

        cin >> totalNations >> remain;

        vector<Nation> nations;
        nations.reserve( totalNations );

        for ( unsigned int j = 0; j < totalNations; ++j )
        {
            int gold = 0;
            int silver = 0;
            int bronze = 0;

            cin >> gold >> silver >> bronze;
            nations.emplace_back( gold, silver, bronze );
        }

        simulateBestRankWay1( nations, remain );
        simulateBestRankWay2( nations, remain );
    }
}

    8년 전
0개의 댓글이 있습니다.

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