C++로 수학 경시 대회 승자 판별하기 — Amal vs Bimal 점수 계산 알고리즘

문제 설명

크기가 n인 두 배열 P와 T, 그리고 정수 c가 주어집니다. Amal과 Bimal은 n개의 문제로 구성된 수학 경시 대회에 참가합니다. i번째 문제의 초기 배점은 P[i]이고, 푸는 데 걸리는 시간은 T[i]입니다. 두 배열은 모두 오름차순으로 정렬되어 있으며, c는 분당 감점 계수입니다. 대회 시작 후 x분째에 문제를 제출하면 해당 문제에서 max(0, P[i] − c × x)점을 받게 됩니다.

Amal은 문제를 1번부터 n번까지 순서대로 풀고, Bimal은 n번부터 1번까지 역순으로 풉니다. 우리가 할 일은 누가 더 높은 최종 점수를 얻는지 판별하는 것이며, 두 사람의 점수가 같다면 "Tie"(무승부)를 출력해야 합니다.

예를 들어 c = 2, P = [50, 85, 250], T = [10, 15, 25]가 입력으로 주어지면 결과는 Amal입니다.

접근 방법

이 문제는 두 참가자의 점수를 각각 시뮬레이션한 뒤 비교하는 방식으로 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.

누적 시간 추적: 변수 m에 지금까지 소요된 총 시간을 저장합니다.
Amal 점수 계산: 배열을 앞에서부터 순회하며 각 문제마다 max(0, P[i] − c × m)를 ans1에 더합니다.
Bimal 점수 계산: 배열을 뒤에서부터 순회하며 같은 방식으로 ans2를 계산합니다.
결과 판정: ans1 > ans2이면 "Amal", ans1 < ans2이면 "Bimal", 그렇지 않으면 "Tie"를 반환합니다.

의사코드

n := P의 크기
m := 0, ans1 := 0, ans2 := 0
i := 0부터 i < n까지 반복:
    m := m + T[i]
    ans1 := ans1 + max(0, P[i] - c * m)
m := 0
i := n - 1부터 i >= 0까지 반복:
    m := m + T[i]
    ans2 := ans2 + max(0, P[i] - c * m)
ans1 > ans2이면 "Amal" 반환
ans1 < ans2이면 "Bimal" 반환
그 외에는 "Tie" 반환

C++ 구현 예제

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

string solve(int c, vector<int> P, vector<int> T){
    int n = P.size();
    int m = 0, ans1 = 0, ans2 = 0;
    // Amal: 정방향(1 → n)으로 풀이
    for (int i = 0; i < n; i++){
        m += T[i];
        ans1 += max(0, P[i] - c * m);
    }
    // Bimal: 역방향(n → 1)으로 풀이
    m = 0;
    for (int i = n - 1; i >= 0; i--){
        m += T[i];
        ans2 += max(0, P[i] - c * m);
    }
    if (ans1 > ans2)
        return "Amal";
    else if (ans1 < ans2)
        return "Bimal";
    else
        return "Tie";
}

int main(){
    int c = 2;
    vector<int> P = { 50, 85, 250 };
    vector<int> T = { 10, 15, 25 };
    cout << solve(c, P, T) << endl;
}

주의할 점은 Bimal이 모든 문제를 풀어야 하므로 역방향 반복문의 종료 조건이 i >= 0이 되어야 한다는 것입니다. 조건을 잘못 설정하면 특정 문제가 점수 계산에서 누락될 수 있습니다.

실행 결과

입력

2, { 50, 85, 250 }, { 10, 15, 25 }

출력

Amal

결과 분석

실제 계산 과정을 살펴보겠습니다.

Amal (정방향):
1번 문제: x = 10분 제출 → max(0, 50 − 20) = 30점
2번 문제: x = 25분 제출 → max(0, 85 − 50) = 35점
3번 문제: x = 50분 제출 → max(0, 250 − 100) = 150점
총점: 215점

Bimal (역방향):
3번 문제: x = 25분 제출 → max(0, 250 − 50) = 200점
2번 문제: x = 40분 제출 → max(0, 85 − 80) = 5점
1번 문제: x = 50분 제출 → max(0, 50 − 100) = 0점
총점: 205점

Amal이 215점으로 Bimal의 205점보다 10점 높으므로 최종 결과는 Amal입니다. 흥미롭게도 고배점 문제를 먼저 푸는 Bimal의 전략이 유리해 보이지만, 나머지 문제들이 감점으로 인해 거의 0점 처리되면서 오히려 손해를 보게 됩니다.

복잡도 분석

두 배열을 각각 한 번씩만 순회하므로 시간 복잡도는 O(n)이며, 추가 자료구조 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 문제 수가 많아져도 매우 효율적으로 동작합니다.