이 문제에서는 크기가 n인 배열 stu[]가 주어지며, 이 배열에는 반 학생들의 시험 점수가 담겨 있습니다. 각 학생의 만점은 100점이며, 시험에 합격하려면 최소 50점을 받아야 합니다. 우리의 목표는 모든 학생에게 보너스 점수를 지급하되 어떤 학생의 점수도 100점을 초과하지 않도록 하면서, 합격시킬 수 있는 학생의 최대 인원수를 구하는 프로그램을 작성하는 것입니다.
문제 설명
학생들이 시험에 합격할 수 있도록 보너스 점수를 지급해야 하며, 여기서 중요한 조건은 보너스가 모든 학생에게 동일하게 지급되어야 한다는 점입니다. 또한 보너스를 지급한 후 어떤 학생의 점수도 100점을 넘어서는 안 됩니다. 이러한 조건을 만족하면서 합격자 수를 최대화하고, 그 결과를 반환하면 됩니다.
예제를 통해 문제 이해하기
입력
stu[] = {45, 32, 78, 10, 53, 67}출력
5
설명
합격한 학생들 : 45 + 22 = 67 32 + 22 = 54 78 + 22 = 100 53 + 22 = 75 67 + 22 = 89
가장 높은 점수가 78점이므로 지급할 수 있는 최대 보너스는 22점입니다. 22점을 모두에게 더했을 때 50점 이상이 되는 학생은 총 5명이며, 이것이 곧 정답입니다.
해결 접근 방식
이 문제를 해결하려면 학생들에게 점수를 더해주면 되지만, 한 가지 반드시 고려해야 할 사항이 있습니다. 바로 가장 높은 점수를 가진 학생의 점수가 100점을 초과해서는 안 된다는 것입니다.
따라서 지급 가능한 최대 보너스는 다음과 같이 계산할 수 있습니다.
최고 점수 학생(M) + 보너스 = 100 보너스 = 100 − M
이렇게 계산된 보너스를 모든 학생의 현재 점수에 더한 뒤, 그 값이 50점 이상이라면 해당 학생은 합격합니다. 최종 결과는 이러한 학생들의 수를 세면 됩니다.
알고리즘
초기화
passCount = 0;
1단계 −
가장 높은 점수를 가진 학생(maxMarks)을 찾습니다.
2단계 −
모든 학생에게 지급할 보너스를 계산합니다. bonus = 100 − maxMarks
3단계 −
i → 0부터 n−1까지 반복합니다.
3.1단계 −
if(stu[i] + bonus >= 50) 이면 passCount++ 합니다.
4단계 −
passCount를 반환합니다.
예제 코드
풀이 과정을 보여주는 프로그램입니다.
#include<iostream>
using namespace std;
int calcPassCount(int stu[], int n) {
int maxMarks = stu[0];
for(int i = 1; i < n; i++){
if(stu[i] > maxMarks)
maxMarks = stu[i];
}
int bonusMarks = 100 − maxMarks;
int passCount = 0;
for(int i=0; i<n; i++) {
if(stu[i] + bonusMarks >= 50)
passCount ++;
}
return passCount;
}
int main() {
int stu[] = {45, 32, 78, 10, 53, 67};
int n = sizeof(stu)/sizeof(stu[0]);
cout<<"모든 학생에게 보너스를 지급한 후 합격할 수 있는 최대 학생 수 : "<<calcPassCount(stu, n);
return 0;
}출력
모든 학생에게 보너스를 지급한 후 합격할 수 있는 최대 학생 수 : 5
이 알고리즘은 먼저 최댓값을 찾는 O(n) 연산과 합격자를 세는 O(n) 연산을 수행하므로, 전체 시간 복잡도는 O(n)이며 추가 공간 복잡도는 O(1)입니다. 따라서 매우 효율적으로 문제를 해결할 수 있습니다.