백준 12760번 [최후의 승자는 누구?](C++) -yes6686- 티스토리

백준 문제 풀이: 12760 (최후의 승자는 누구?)

---

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

문제 설명:

n명의 참가자가 m개의 카드를 가지고 있다. 각 참가자는 자신이 가진 카드 중에서 높은 값이 많을수록 유리하다. 모든 카드 위치(j번째 카드)에서 최고값을 가진 참가자에게 1점을 부여한다. 모든 위치에 대해 점수를 합산한 뒤, 가장 높은 점수를 가진 참가자가 최후의 승자가 된다. 동점자가 있다면 모두 출력한다.

---

문제 해결 코드

// 12760번: 최후의 승자는 누구?
// 각 열마다 최대값을 가진 사람에게 점수를 부여하고, 최고 점수를 받은 사람(들)을 출력

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

int arr[101][101];     // 참가자의 카드 정보
int cmax[101];         // 각 열(카드 위치)별 최대값 저장
int cnt[101];          // 참가자별 점수 카운트

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

    int n, m;
    cin >> n >> m;

    // 카드 입력 및 각 참가자의 카드 정렬 (내림차순은 필요 없음, 열 기준 최대값 비교용)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
        sort(arr[i], arr[i] + m);  // 정렬은 필수가 아님, 출력과 무관
    }

    // 각 열(카드 위치)에서 최대값 구하기
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            cmax[j] = max(cmax[j], arr[i][j]);
        }
    }

    // 최대값과 일치하는 값을 가진 참가자에게 점수 부여
    int maxCnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == cmax[j]) {
                cnt[i]++;
            }
        }
        maxCnt = max(maxCnt, cnt[i]);
    }

    // 최종 승자 출력
    for (int i = 0; i < n; i++) {
        if (cnt[i] == maxCnt) {
            cout << i + 1 << " ";  // 인덱스를 1부터 출력
        }
    }
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘: 각 카드 위치별로 최대값을 기록하고, 이를 기준으로 점수를 집계하는 완전 탐색 방식.
• 구현 세부사항:
  • arr[i][j]: i번 참가자의 j번째 카드값
  • cmax[j]: j번째 카드 위치의 전체 참가자 중 최대값
  • cnt[i]: i번 참가자가 얻은 총 점수
• 시간 복잡도 분석:입력: O(n ⋅ m), 각 열 최대값 탐색: O(n ⋅ m), 점수 계산: O(n ⋅ m)
• 총 시간 복잡도: O(n ⋅ m)

---

결과

카드 위치별 최고값을 기준으로 점수를 집계한 결과, 가장 높은 점수를 받은 참가자의 번호(1-based index)를 출력합니다.

예시 입력:
3 4
1 7 3 4
5 1 2 6
1 4 3 2

예시 출력:
1

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!