n개의 요소를 가진 배열 A와 숫자 m이 주어져 있다고 가정해 봅시다. n명의 학생이 시험을 응시하고 있으며, 받을 수 있는 최고 점수는 m입니다. A[i]는 i번째 학생의 점수를 의미합니다. 우리는 각 학생의 점수를 조정할 수 있지만, 반드시 다음 세 가지 조건을 만족해야 합니다.
- 점수는 m을 초과할 수 없습니다.
- 모든 점수는 정수여야 합니다.
- 전체 학생의 평균 점수는 변하지 않아야 합니다.
이러한 조건에서 첫 번째 학생에게 부여할 수 있는 가장 높은 점수는 얼마일까요?
예제로 이해하기
입력이 A = [1, 2, 3, 4], m = 10이라고 해보겠습니다. 현재 점수의 평균은 2.5입니다. 이때 점수를 [10, 0, 0, 0]으로 재설정하면 평균은 그대로 2.5로 유지되면서 첫 번째 학생의 점수가 최대가 됩니다. 따라서 출력은 10입니다.
문제 풀이 접근법
핵심 아이디어
평균 점수가 변하지 않아야 한다는 조건은 사실상 전체 점수의 합이 일정하게 유지되어야 한다는 의미입니다. 학생 수는 고정되어 있기 때문에, 총합이 같다면 평균도 자동으로 동일하게 유지됩니다.
따라서 첫 번째 학생이 받을 수 있는 이론상 최대 점수는 나머지 학생들이 모두 0점을 받는 경우, 즉 전체 점수의 합(sum)과 같습니다. 동시에 점수는 m을 초과할 수 없으므로, 최종 답은 m과 sum 중 더 작은 값이 됩니다.
알고리즘 단계
- 배열 A의 모든 요소를 더하여 총합(sum)을 계산합니다.
- m과 sum 중 최솟값을 반환합니다.
의사 코드로 표현하면 다음과 같습니다.
sum := 0 n := size of A for initialize j := 0, when j < n, update (increase j by 1), do: sum := sum + A[j] return minimum of m and sum
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int m){
int sum = 0;
int n = A.size();
for (int j = 0; j < n; j++){
sum += A[j];
}
return min(m, sum);
}
int main(){
vector<int> A = { 1, 2, 3, 4 };
int m = 10;
cout << solve(A, m) << endl;
}
입력
{ 1, 2, 3, 4 }, 10
출력
10
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 공간 없이 총합만 저장하므로 공간 복잡도는 O(1)입니다. 매우 효율적인 해결 방식이라고 할 수 있습니다.