문제
각 학교의 학생 수와 사과 수가 주어질 때, 사과를 학생에게 균등 배분 후 남는 사과의 총합을 구하라.
입력
학교 수 N, 각 학교의 학생 수와 사과 수가 주어진다.
출력
모든 학교에서 남는 사과의 총합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 25 70 ## 110 35 90 | 47 |
풀이
각 학교의 나머지를 합산한다.
- 각 학교에 대해
사과 % 학생을 계산한다 - 모든 나머지를 합산하여 출력한다
핵심 아이디어: 나머지 연산으로 O(N)에 해결된다.
코드
#include <iostream>
using namespace std;
int main()
{
int student, apple, num, sum = 0;
cin >> num;
for (int i = 0; i < num; i++)
{
cin >> student >> apple;
sum += apple % student;
}
cout << sum << '\n';
}복잡도
- 시간: O(N) (N: 학교 수)
- 공간: O(1)