백준 3758번 [KCPC](C++) -yes6686- 티스토리

백준 문제 풀이: 3758 [KCPC]

---

문제 링크: https://www.acmicpc.net/problem/3758

문제 설명:

국제 대학생 프로그래밍 대회(KCPC)의 온라인 예선을 진행하는 과정에서, 특정 팀 t의 최종 순위를 구하는 문제입니다.

채점 로그를 통해 팀별 최고 점수를 관리하고, 순위 결정 기준에 따라 최종 랭킹을 산출합니다.

순위 결정 기준:

1. 총점이 높은 팀이 높은 순위를 가짐
2. 총점이 같다면 제출 횟수가 적은 팀이 높은 순위를 가짐
3. 총점과 제출 횟수가 같다면 마지막 제출 시간이 빠른 팀이 높은 순위를 가짐

---

문제 해결 코드

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

pair<int, pair<int, int>> arr[101]; // {총점, {제출 횟수, 마지막 제출 시간}}
pair<int, pair<int, int>> tarr[101]; // 특정 팀의 최종 기록 저장
int sarr[101][101]; // 팀별 문제별 최고 점수 저장

// 정렬 기준 정의
bool compare(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    if (a.first == b.first) {
        if (a.second.first == b.second.first) {
            return a.second.second < b.second.second; // 마지막 제출 시간이 짧은 팀 우선
        }
        return a.second.first < b.second.first; // 제출 횟수가 적은 팀 우선
    }
    return a.first > b.first; // 총점이 높은 팀 우선
}

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

    int T;
    cin >> T; // 테스트 케이스 개수 입력
    while (T--) {
        int n, k, t, m;
        cin >> n >> k >> t >> m; // 팀 개수, 문제 개수, 순위를 알고 싶은 팀, 로그 개수 입력

        for (int i = 0; i < m; i++) {
            int a, b, s;
            cin >> a >> b >> s; // 팀 번호 a, 문제 번호 b, 획득 점수 s 입력

            // 해당 팀의 문제 점수 갱신 (기존 점수보다 높을 경우만 반영)
            if (sarr[a][b] < s) {
                arr[a] = { arr[a].first - sarr[a][b] + s, {arr[a].second.first + 1, i} };
                sarr[a][b] = max(sarr[a][b], s);
            } else {
                arr[a] = { arr[a].first, {arr[a].second.first + 1, i} };
            }
            tarr[a] = arr[a]; // 현재 상태를 저장
        }

        // 팀 순위 정렬
        sort(arr + 1, arr + n + 1, compare);

        // 팀 t의 순위 찾기
        for (int i = 1; i <= n; i++) {
            if (arr[i] == tarr[t]) {
                cout << i << '\n';
                break;
            }
        }

        // 배열 초기화
        memset(arr, 0, sizeof(arr));
        memset(tarr, 0, sizeof(tarr));
        memset(sarr, 0, sizeof(sarr));
    }
}

예제 입력:

1
3 4 2 7
1 1 10
2 1 20
3 1 30
1 2 40
2 2 50
3 2 60
2 3 70

예제 출력:

1

---

코드 설명

• 핵심 알고리즘: 정렬을 활용한 랭킹 산출
• 구현 세부사항:
  • 배열 sarr에 팀별 최고 점수를 저장하여 총점 계산
  • 팀별 총점, 제출 횟수, 마지막 제출 시간을 기록하여 순위 정렬
  • 정렬 후 팀 t의 순위를 출력
• 시간 복잡도: O(M + N log N), 정렬 연산 포함

---

결과

입력된 점수 로그를 기반으로 팀의 점수를 갱신하고, 순위 기준에 맞춰 정렬하여 정확한 순위를 계산합니다. 정렬을 활용한 문제 해결을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!