C++ 예제 (넥슨 프로그래밍 대회 문제풀이 1)

오늘은 전년도 2018년 넥슨 청소년 프로그래밍 대회(NYPC) 예선 문제를 C++로 만들어 보았습니다.

대회 진행방식은 온라인으로 예선문제를 풀어 제출하고, 이중 본선진출자를 선정해 넥슨판교사옥에서 본선을 진행한다고 합니다.

자세한 2019년 대회 소개 및 일정은 아래 내용과 링크 사이트를 통해 참조 바랍니다.

대상 : 12세 ~19세 누구나

참가 언어 : 파이썬, 자바, C#, C, C++

링크 : NYPC 2019

그럼, NYPC 2018 예선 첫번째 문제풀이 입니다.

다른 문제풀이는 아래 링크를 참조해 주세요.

예선 문제 풀이 2

예선 문제 풀이 3

예선 문제 풀이 4

첫 문제라 다른 문제에 비해 난이도는 쉬운편입니다.

[문제 1 : 아이템 구매]

게임개발자 상현이가 개발 중인 게임의 상점에는 체력 물약과 마나 물약 두 종류의 아이템만 판매하고 있다. 상현이는 유저들의 판매 로그를 기록해야하는데, 실수로 그만 유저들이 상점에서 사용한 총액만 기록하고 말았다.

체력 물약의 가격은 P원이고, 마나 물약 가격은 Q원이다. 그리고 한 유저가 상점에서 사용한 총액은 W원이다. 상현이를 도와 유저가 상점에서 구매한 아이템 개수를 구하는 프로그램을 작성하시오.

[풀이]

알고리즘 문제는 문제를 정확히 이해하는 것이 중요합니다.

한마디로, 물약(체력, 마나)의 가격과 전체 총액은 아는데 구입 개수가 몇 개인지 구하라는 문제입니다.
(단, 1<= 물약의 개수 <= 500,000 , and 해가 여러개인 경우 아무 답이나 출력)

예) 체력물약가격 : 9, 마나물약 가격 : 7 , 총액 : 55

방정식을 세워보면 9x + 7y = 55,

미지수의 개수(x, y)가 식의 수(1) 보다 많으므로 부정방정식을 푸는 문제입니다.

풀어보면, 방정식의 해는 x = 3, y = 4 입니다. (9x3 + 7x4 = 55)

수식 유도 과정은 아래와 같습니다.

ax + by = c
by = c - ax
y = (c-ax) / b

수식이 이해가 되었다면, 이제 C++ 코드로 옮겨 보겠습니다.

#include < iostream >

using namespace std;

int main()
{
    // 체력 물약 : p, 마나물약 : q, 총액 : w
    int p = 0, q = 0, w = 0;

    // 공백으로 3가지 대입 받기(체력, 마나, 총액)
    cin >> p >> q >> w;

    // y에 대한 방정식
    // 1. ax + by = c 
    // 2. by = c-ax
    // 3. y = (c-ax)/b

    for (int i = 1; i * p <= w; i++) 
    {  
         if ((w - (i * p)) % q == 0)
         {
             cout << i << " " << (w - (i * p)) / q << endl;
             break;
         }
    }
     return 0;
}

먼저 8번라인에 각 변수를 선언하고, 대입 받습니다.

체력물약가격 : p, 마나물약가격 : q, 전체물약 총액 : w

순서는 체력물약가격, 마나물약가격, 전체물약총액 순서입니다. (예 9, 7, 55)

물약의 개수는 정수이므로, 반복문을 통해 x를 1씩 증가시키며 나누어 떨어지는 y를 찾습니다.

만약 나머지가 없다면, 해를 찾은 것이므로 답(해)을 출력합니다.

코드에서 i (x)는 체력물약의 개수이며, (w - (i x p)) / q는 y를 의미합니다.

부정방정식의 경우 해가 여러개 일 수 있는데, 문제 조건에서 해는 아무거나 출력해도 상관없다는 조건이 붙어 있으므로 break 명령어를 통해 즉시 반복문을 탈출합니다.

아래는 위 코드의 실행결과 입니다.

입력 : 2 3 10 (HP가격 2, MP가격 3, 물약총액, 10)
출력 : 2 2 (HP물약 2개, MP물약 2개, 2 x 2 + 3 x 2 = 10)

하나 더 풀어볼까요?

두번째 문제는 좀 더 어렵습니다.

[문제 2 : 승리 팀 찾기]

우성이는 카트라이더를 즐기는 유저이다. 우성이는 항상 친구가 많기 때문에 개인전 보다는 팀전을 즐겨 한다. 게임의 종류와 플레이어들의 도착시간이 주어졌을 때, 어느 팀이 이겼는지를 계산하는 프로그램을 만들어 보자.

카트라이더는 아이템전과 스피드전이 있다. 팀은 레드 팀과 블루 팀이 있으며, 문제 편의상 항상 4:4 게임만 진행되었다고 가정한다.
아이템전은 1등으로 들어온 사람이 속한 팀이 승리한다.

스피드전은 등수별로 점수를 합산하여 더 높은 점수를 획득한 팀이 승리한다.

A. 만약 점수가 같다면, 1등으로 들어온 사람이 속한 팀이 승리한다.
B. 등수 별 획득 점수는 아래와 같다.

1등	10점
2등	8점
3등	6점
4등	5점
5등	4점
6등	3점
7등	2점
8등	1점
리타이어(*)	0점

 C. 1등과 10초 이상 차이가 나면 리타이어로 0점을 획득한다.

[풀이]

문제 내용을 이해하기가 조금 어렵습니다. 링크 사이트에서 자세히 읽어 보기 바랍니다.

4:4 팀 플레이 게임 (red 팀 4명, blue 팀 4명)
게임 수 입력 (2 게임, 3게임 등)
게임의 종류 입력 (아이템전 or 스피드전)
게임 결과 입력 8명 (소속팀, 기록 예 red 1:22.12, blue 1:26.32)
승리팀 결과 출력 (red or blue)

입력 예제 1

2
item
blue 2:01.12
red 2:13.44
red 1:56.33
blue 2:03.31
red 2:04.84
red 2:06.67
blue 1:58.14
blue 2:07.31
speed
blue 2:01.12
red 2:13.44
red 1:56.33
blue 2:03.31
red 2:04.84
red 2:06.67
blue 1:58.14
blue 2:07.31

출력 예제 1

red
blue

설명:

첫 번째 경기는 아이템전이고 3번 플레이어가 제일 먼저 들어왔으므로 red팀이 승리한다.

두 번째 경기는 스피드전이고, 3->7->1->4->5->6->8->2 번 순서대로 골인하였지만 6, 8, 2번 유저는 10초 이상 차이가 나서 리타이어로 점수를 받을 수 없다. red 팀은 10 + 4 = 14 점이고, blue 팀은 8 + 6 + 5 = 19 점을 획득하여 blue팀이 승리한다.

이해가 되었나요?

자세한 설명은 아래 C++코드를 보며 진행하겠습니다.

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

using namespace std;

// 팀별 선수 수
const int n = 4;
const int score[] = { 10, 8, 6, 5, 4, 3, 2, 1 };

// 선수 클래스
class CPlayer
{
public:
    CPlayer(bool t = true, int ra = 0, double rec = 0, int s = 0)
    {
        team = t;
        rank = ra;
        record = rec;
        score = s;
    }
    ~CPlayer() {}

public:
    bool team; // red : true, blue : false
    int rank;
    double record;
    int score;
};

// 게임 클래스
class CGame
{
public:
    CGame(bool t = true, bool win = true) :players(n * 2)
    {
        type = t;
        winner = win;
        redScore = blueScore = 0;
    }
    ~CGame() {}

public:
    bool type;// item:true, speed:false
    bool winner;// red : true, blue : false
    vector<CPlayer> players;
    int redScore, blueScore;

    static bool sortRank(const CPlayer& p1, const CPlayer& p2)
    {
        return p1.record < p2.record;
    }
    void update()
    {
        //먼저 기록 정렬
        std::sort(players.begin(), players.end(), sortRank);

        int order = 0;
        double bestRec = 0;

        vector<CPlayer>::iterator itr;
        for (itr = players.begin(); itr != players.end(); ++itr)
        {
            // 1등 기록 
            if (order == 0)
                bestRec = itr->record;

            // 1등기록과 10초이상 차이나면 0점
            if (itr->record >= bestRec + 10.0)
                itr->score = 0;
            else
                itr->score = score[order];

            // 팀별 점수 합산
            if (itr->team)
                redScore += itr->score;
            else
                blueScore += itr->score;

            order++;
            itr->rank = order;

            //cout << itr->team << " " << itr->rank << " " << itr->record << " " << itr->score << endl;            
        }

    }
    string getWinner()
    {
        string winner;
        // item
        if (type == true)
        {
            if (players.at(0).team == true)
                winner = "red";
            else
                winner = "blue";
        }
        else // speed
        {
            if (redScore == blueScore)
            {
                if (players.at(0).team)
                    winner = "red";
                else
                    winner = "blue";
            }
            else if (redScore > blueScore)
                winner = "red";
            else
                winner = "blue";
        }
        return winner;
    }
    static double getTimeRecord(const string& strRec, char c)
    {
        string str;
        double fRec = 0;
        int token = strRec.find(c);
        str = strRec.substr(0, token);
        fRec = atof(str.c_str());
        str = strRec.substr(++token, strRec.length());
        fRec = (fRec*60.0 + atof(str.c_str()));

        return fRec;
    }
};


int main()
{
    // 테스트 케이스의 수
    int t = 0;
    cin >> t;

    // 게임 기록 입력
    vector<CGame> game(t);
    for (int i = 0; i < t; i++)
    {
        string type;
        cin >> type;

        // 게임종류
        if (type == "item")
            game.at(i).type = true;
        else
            game.at(i).type = false;

        // 팀종류, 선수기록 저장
        for (int k = 0; k < n * 2; k++)
        {
            string team, rec;
            cin >> team >> rec;

            game.at(i).players.at(k).record = CGame::getTimeRecord(rec, ':');

            if (team == "red")
                game.at(i).players.at(k).team = true; // red            
            else
                game.at(i).players.at(k).team = false; // red
        }
    }

    // 게임 결과 출력
    vector<CGame>::iterator itr;
    for (itr = game.begin(); itr != game.end(); ++itr)
    {
        // 게임결과 입력값 정렬, 점수 및 순위 계산
        itr->update();
        cout << itr->getWinner() << endl;
    }

    return 0;
}

이제 코드 분석에 들어가 보겠습니다.

1~4번 라인은 필요한 헤더 파일을 포함시키는 전처리기 구문입니다.

파이썬의 import 구문과 같은 역할의 C++ 명령어 입니다.

그 다음으로 팀별 선수 수(4명)을 n이라는 const 변수로 저장해 수정이 불가하도록 합니다.

이어서 10번 라인에 score[] 배열을 생성해 순위별 점수(1등 10점 2등 8점 ...)를 저장해 둡니다.

변수의 타입 앞에 const 를 붙여 생성하면, 그 변수는 값을 선언시 지정한 값 외 변경이 불가합니다.

자 이제 카트라이더의 게이머를 의미하는 CPlayer 클래스를 만듭니다.

CPlayer의 멤버 변수를 다음의 역할을 담당합니다.

team, (어떤 팀인지 bool type, true:red, false:blue)
rank, (몇 등인지 int type)
record, (기록, double type)
score, (기록에 따른 점수, int type)

33번 라인은 게임 결과를 처리, 판정하는 CGame Class 입니다.

CGame Class의 멤버 변수는 아래와 같습니다.

type (아이템전 or 스피드전, bool type)
winner (승리 팀 red or blue, bool type)
vector<CPlayer> players (모든 선수 정보, vector<CPlayer> type)
red, blue Score (각 팀별 점수합산, int type)

다음은 Member Function (Method) 입니다.

static bool sortRank() (기록 오름차순 정렬 용도)
void update() (플레이어 기록 근거로 순위, 개인점수, 팀별 점수합산)
string getWinner() (아이템전 or 스피드전 승리팀 판정)
double getTimeRecord() (입력받은 기록문자를 숫자로 변환)

두 클래스를 요약하면 CPlayer 클래스는 각 선수가 가지는 속성이나 행위를 저장하는 타입이며, CGame 클래스는 CPlayer 타입의 변수를 멤버 변수로 가지며(has-A 구조), 각 플레이어의 기록을 정렬하고, 점수를 계산해 승리 여부를 판정하는 클래스 입니다.

이제 130번 라인 메인 함수를 살펴보겠습니다.

아래의 순서대로 코드를 수행해 승리팀을 판별하게 됩니다.

게임 횟수를 입력 (133번 라인)
게임 클래스의 변수 선언 (137번 라인)
게임 횟수 만큼 반복문 시작 (138번 라인)
게임 종류 입력 (144번 라인, item or speed)
각 선수에 대한 정보 입력 (150~161번 라인, red or blue, record)
게임 별 승리팀 판정, 출력 (165~171번 라인)

어려운 부분은 없지만 115번 라인 CGame::getTimeRecord() 함수는 문자열 파싱관련 함수이므로 주의깊게 살펴볼 필요가 있습니다.

예를 들어 "1:23.45" 이라는 문자열 변수를 정수형으로 변환을 해야 합니다.

그래야만 선수들의 기록을 비교 (크다, 작다)해 순위 판정이 가능하기 때문이죠.

저는 ':'이라는 문자기호를 찾아 앞자리 수에 60을 곱해 초단위로 변경한 후 ':'의 뒷자리와 더하는 방식을 사용하였습니다.

예) 문자열 입력 "1:23.34" 변환 과정

':' 문자 기준 왼쪽 글자 얻기 (1 입니다)
':' 문자 기준 오른쪽 글자 얻기 (23.34 입니다)
"1" , "23.34" 문자열 atof()함수 이용 숫자 변환
(1 x 60) + 23.34 = 83.34 초 기록 얻기

아래는 실제 코드 입, 출력 결과 입니다.

참고로 소요시간의 경우, 1번 문제는 해결(문제파악, 코드작성, 테스트)에 10분이 걸렸으며, 2번 문제는 1시간 정도 소요되었습니다.

이상으로 2018 NYPC 예선 문제에 대한 분석을 마칩니다.

감사합니다.

이 블로그 검색

오션코딩학원