백준 2303번 [숫자 게임](C++) -yes6686- 티스토리

백준 문제 풀이: 2303 (숫자 게임)

---

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

문제 설명:

여러 명의 참가자가 5장의 카드를 가지고 숫자 게임을 합니다. 각 참가자는 **5장의 카드 중 2장을 제외**한 나머지 3장의 카드의 합을 구합니다. 합을 **10으로 나눈 나머지**가 가장 큰 사람이 이기며, 동점일 경우 **가장 뒤에 등장한 참가자가 우승**합니다. 결과적으로 **우승자의 번호**를 출력해야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[5]; // 각 참가자의 카드 5장을 저장할 배열

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

    int n; // 참가자 수
    cin >> n;

    int maxIndex = 1; // 우승자의 번호 (초기값 1번 참가자)
    int maxAns = -1;  // 가장 큰 나머지 값 (초기값 -1)

    for (int i = 0; i < n; i++) {
        int totalSum = 0;

        // 카드 입력 및 총합 계산
        for (int t = 0; t < 5; t++) {
            cin >> arr[t];
            totalSum += arr[t];
        }

        // 두 장을 제외한 세 장의 합을 구하고 10으로 나눈 나머지를 계산
        for (int h = 0; h < 5; h++) {
            for (int j = h + 1; j < 5; j++) {
                int remainder = (totalSum - arr[h] - arr[j]) % 10;

                // 최대 나머지 값 갱신 및 참가자 번호 저장
                if (maxAns <= remainder) { // 동점일 경우 뒤 참가자 우선
                    maxAns = remainder;
                    maxIndex = i + 1; // 참가자 번호는 1부터 시작
                }
            }
        }
    }

    // 우승자의 번호 출력
    cout << maxIndex;
    return 0;
}

---

코드 설명

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

• 카드 입력 및 총합 계산: 각 참가자는 **5장의 카드**를 입력받고 총합을 계산합니다.
• 두 장을 제외한 나머지 3장의 합:
  • 두 장의 카드 arr[h]와 arr[j]를 제외한 합을 구합니다.
  • 합을 **10으로 나눈 나머지**를 계산합니다.
• 최대 나머지 비교: - **최대 나머지 값**을 갱신하며, 동점인 경우에는 **뒤에 나온 참가자**의 번호를 저장합니다.

시간 복잡도 분석

• 참가자 수를 n이라 하고, 각 참가자는 **O(5×4/2 = 10)**번의 연산을 수행합니다.
• 따라서 전체 시간 복잡도는 **O(n × 10)** = **O(n)**입니다.

---

결과

입력된 카드 값들 중 조건을 만족하는 **최대 나머지를 가진 참가자의 번호**를 출력합니다.

• 입력 예시:

  2  
  1 2 3 4 5  
  5 5 5 5 5

• 출력 예시:

  2

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