문제출처: https://www.acmicpc.net/problem/2535
문제
최근 아시아 지역의 학생들만 참여하는 정보 올림피아드 대회가 만들어졌다. 이 대회는 온라인으로 치러지기 때문에 각 나라에서 이 대회에 참여하는 학생 수의 제한은 없다.
참여한 학생들의 성적순서대로 세 명에게만 금, 은, 동메달을 수여한다. 단, 동점자는 없다고 가정한다. 그리고 나라별 메달 수는 최대 두 개다.
예를 들어, 대회 결과가 다음의 표와 같이 주어졌다고 하자.
이 경우, 금메달 수상자는 1번 국가의 1번 학생이고, 은메달 수상자는 1번 국가의 2번 학생이며, 동메달 수상자는 3번 국가의 4번 학생이다. (1번 국가의 3번 학생의 성적이 동메달 수여자보다 높지만, 나라 별 메달 수가 두 개 이하 이므로 1번 국가 3번 학생은 동메달을 받을 수 없다.)
대회 결과가 입력으로 주어질 때, 메달 수상자를 결정하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 대회참가 학생 수를 나타내는 N이 주어진다. 단, 3<=N<=100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사이에 두고 주어진다. 단, 국가 번호는 1부터 순서대로 하나의 정수로 주어지며, 각 학생번호는 각 나라별로 1부터 순서대로 하나의 정수로 주어진다, 점수는 0 이상 1000 이하의 정수이고, 동점자는 없다고 가정한다. 입력으로 제공되는 국가는 적어도 두 나라 이상이다.
출력
메달을 받는 학생들을 금, 은, 동메달 순서대로 한 줄에 한 명씩 출력한다. 즉, 첫 번째 줄에는 금메달 수상자를, 두 번째 줄에는 은메달 수상자를, 세 번째 줄에는 동메달 수상자를 출력한다. 하나의 줄에는 소속국가 번호와 학생 번호를 하나의 빈칸을 사이에 두고 출력한다.
풀이
구조체+정렬 문제로써, c언어 구조체스타일로 구현할 수 있지만 이럴 때 클래스를 안쓰면 나중에 까먹을까봐 클래스로 구현했습니다.
25행까지는 무리없이 이해가 가실거고, 같은나라에서 두개의 메달이나왔을 때 세번째 메달의 순위를 구하는 방법을 알아봅시다.
방법은 간단합니다. 학생 수가 3~100까지므로 학생이속한 나라의 메달 갯수를 저장하기위해 100크기의 1차원배열을 선언합니다.
그리고 42행을 보면, 보기의 예시처럼 1번국가에서 3개의 메달이 나오는것을 방지하기위해 한 국가에서 메달이 2개까지나왔는지를 검사합니다.
참이면 1증가시켜주고 동메달의 점수를 갖는 사람의 국가가 그 국가일 때 건너뛸 수있도록합니다. 그리고 그 연산을 마치고 cnt를 증가시켜주며 3명까지 출력 시킬 수 있도록합니다!
코드
#include<iostream>
#include<algorithm>
using namespace std;
class info
{
public:
int born;
int num;
int score;
info() {}
void setInfo(int born, int num, int score)
{
this->born = born;
this->num = num;
this->score = score;
}
void showInofo()
{
cout << this->born << " " << this->num << endl;
}
bool operator<(const info&stu) const
{
return this->score >stu.score;
}
};
int check[100];
using namespace std;
int main()
{
info stu[100];
int born, num, score;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> born >> num >> score;
stu[i].setInfo(born, num, score);
}
sort(stu, stu + n);
for (int i = 0,cnt=0; i < n&&cnt<3; i++)
{
if (check[stu[i].born] < 2) {
check[stu[i].born]++;
stu[i].showInofo();
cnt++;
}
}
}
결과
