13458 시험감독

문제링크

👍 풀이

처음에는 while문을 이용하여 전부 빼는 방식을 사용했는데 O(N^2)으로 시간초과가 났다.

그래서 수학적으로 좀 더 생각해보면 C만큼 나눠주었을때 몫만큼 더해주면 되고 만약 나머지가 존재한다면 +1 까지 해주면 끝이난다.

참고로 A,B,C전부 백만까지 가능하므로 int형 범위를 벗어난다
즉 출력값 cnt는 longlong형으로 선언해주어야한다.

코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N, B, C;
vector<int> abc;
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int bc;
		cin >> bc;
		abc.push_back(bc);
	}
	cin >> B >> C;

	long long cnt = 0;
	for (int i = 0; i < N; i++) {
		cnt++;
		abc[i] -= B;
		if (abc[i] > 0) {
			cnt+=abc[i] / C;
			if (abc[i]%C > 0) {
				cnt++;
			}
		}

	}
	cout << cnt;
	return 0;
}