C++ 알고리즘: 모든 학생에게 보너스 점수를 지급한 후 합격할 수 있는 최대 학생 수 구하기

이번 튜토리얼에서는 모든 학생에게 동일한 보너스 점수를 지급하되, 어떤 학생도 100점을 초과하지 않는 조건에서 합격할 수 있는 최대 학생 수를 구하는 프로그램을 다룹니다.

문제의 조건은 다음과 같습니다. N명의 학생 점수가 담긴 배열이 주어지며, 각 학생에게 동일한 양의 보너스 점수를 더해야 합니다. 이때 누구도 100점을 넘을 수 없고, 합격 기준은 50점입니다. 목표는 가능한 한 많은 학생이 시험에 합격하도록 만드는 것입니다.

해결 방법

핵심 아이디어는 간단합니다. 가장 높은 점수를 받은 학생이 100점을 초과하지 않아야 하므로, 지급할 수 있는 최대 보너스 점수는 (100 - 최고 점수)입니다. 이 값을 계산한 뒤, 각 학생의 점수에 보너스를 더했을 때 50점 이상이 되는 학생 수를 세면 됩니다.

예제 코드

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

int check(int n, int marks[]) {
    // 배열에서 최고 점수 찾기
    int* x = std::max_element(marks, marks + n);
    // 최고 점수 학생이 100점을 넘지 않도록 하는 최대 보너스
    int bonus = 100 - (int)(*x);
    int c = 0;
    // 보너스 포함 시 50점 이상인 학생 수 카운트
    for(int i = 0; i < n; i++) {
        if(marks[i] + bonus >= 50) c += 1;
    }
    return c;
}

int main() {
    int n = 5;
    int marks[] = {0, 21, 83, 45, 64};
    cout<<check(n, marks)<<endl;
    return 0;
}

실행 결과

3

코드 설명

위 예제에서 학생들의 점수는 {0, 21, 83, 45, 64}이며, 최고 점수는 83점입니다. 따라서 지급할 수 있는 최대 보너스는 100 - 83 = 17점입니다.

각 학생의 점수에 17점을 더하면 다음과 같습니다.

• 0 + 17 = 17점 → 낙제
• 21 + 17 = 38점 → 낙제
• 83 + 17 = 100점 → 합격
• 45 + 17 = 62점 → 합격
• 64 + 17 = 81점 → 합격

결과적으로 총 3명의 학생이 합격할 수 있으며, 프로그램의 출력값과 일치합니다.

시간 복잡도

최고 점수를 찾는 과정에 O(N), 합격자를 카운트하는 과정에 O(N)이 소요되므로 전체 시간 복잡도는 O(N)입니다. 추가적인 공간 복잡도 없이 상수 공간만 사용하는 매우 효율적인 알고리즘입니다.