[C++] 백준 8979: 올림픽

문제

[C++] 백준 8979: 올림픽 SILVER 5
https://www.acmicpc.net/problem/8979

 

---

 

접근 방법

이 문제는 각 국가의 금/은/동 메달 수가 주어졌을 때, 특정 국가 k의 올림픽 순위를 구하는 문제이다.

순위 기준은 아래와 같이 정렬한 뒤,  k가 몇 번째 그룹에 속하는지 계산하면 된다.

1. 금메달 많은 순
2. 금이 같으면 은메달 많은 순
3. 은도 같으면 동메달 많은 순

처음에는 입력을 string으로 저장해서 비교하려고 했는데, 채점이 8점에서 계속 멈췄다.
원인을 고민해보니 문자열로 처리하면서 한 자리 수만 고려한 입력 방식이었고,
두 자리 이상의 숫자가 들어오는 경우 제대로 읽히지 않아 정렬과 비교가 틀어졌던 것이었다.
그래서 입력을 int로 2중 벡터에 받는 방식으로 수정했다.

 

상세 아이디어

1. 입력 저장
각 국가 정보를 [국가번호, 금, 은, 동] 형태로 vector<vector<int>>에 저장한다.

2. 정렬(내림차순)
2중 반복문으로 모든 국가를 비교하며 swap해서 정렬한다.

• 금 비교 후
• 같으면 은 비교
• 은도 같으면 동 비교

3. k의 순위 계산(동점 처리)
정렬된 상태에서 앞에서부터 보면서,

• 현재 국가와 다음 국가의 (금, 은, 동)이 같으면 동점이므로 cnt++
• 다르면 지금까지 쌓인 동점 개수에 따라 ret을 증가시킨다

그리고 국가번호가 k인 위치를 만나면 그때의 ret이 정답이 된다.

 

구현 시 주의할 점

• 동점 처리 시 “같은 메달 수 그룹”을 정확히 묶어 순위를 건너뛰어야 한다.
• medal[i + 1]을 비교하므로 반복 범위가 끝에서 터지지 않도록(경계) 주의해야 한다.
  (현재 코드는 n+1 크기로 잡아두긴 했지만, 안전하게 하려면 범위 체크가 더 명확한 편이 좋다.)

 

---

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0, k = 0;
	cin >> n >> k;

	vector<vector<int>> medal(n + 1, vector<int>(4, 0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			cin >> medal[i][j];
		}
	}

	for (int y = 0; y < n - 1; y++)
	{
		for (int x = y + 1; x < n; x++)
		{
			if (medal[y][1] < medal[x][1]) // 1. 금메달 기준 정렬
				swap(medal[y], medal[x]);
			else if (medal[y][1] == medal[x][1])  
			{
				if (medal[y][2] < medal[x][2])  // 2. 은메달 개수 비교
					swap(medal[y], medal[x]);
				else if (medal[y][2] == medal[x][2])  
				{
					if (medal[y][3] < medal[x][3])  // 3. 동메달 개수 비교
						swap(medal[y], medal[x]);
				}
			}
		}
	}

	int ret = 1;
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		if (medal[i][0] == k)
			break;

		if ((medal[i][1] == medal[i + 1][1]) && (medal[i][2] == medal[i + 1][2])
			&& (medal[i][3] == medal[i + 1][3]))
			cnt++;
		else
		{
			if (cnt == 0)
				ret++;
			else
			{
				ret += (cnt + 1);
				cnt = 0;
			}
		}
	}
	cout << ret;

	return 0;
}