[백준 13458번 / C++] 시험 감독

해당 문제는 브론즈 문제이지만, 두가지의 예외사항이 있기 때문에 포스팅한다. 

 

#접근 방법 

 

로직은 단순하다. 

총 감독관은 각 시험장에 한명씩 투입돼야 하기 때문에 

각 시험장에 수용하는 인원에다가 총 감독관이 감시할 수 있는 인원을 빼주고 시작한다. 

그리고 부감독관이 감시할 수 있는 인원을 나누어주면 부감독관의 인원이 나온다. 

그리고 나누었을 때 나머지가 1 이상이라면 한 명의 부감독관이 추가돼야한다. 

 

여기서 예외사항이 있다. 

 

총감독관이 모든 시험장에 투입됐는데 총감독관 혼자서 모든 인원을 감시할 수 있다면 부감독관을 고용할 필요가 없다는 뜻이다. 그렇기 때문에 각 시험장에서 수용하는 인원에서 총감독관이 감시할 수 있는 인원을 뺐을 때 

해당 인원수가 0 이하로 떨어진다면 부감독관의 투입을 고려하지말자. 

 

두번째는 최악의 상황을 고려하자. 

1,000,000의 강의실에 1,000,000의 인원을 수용시킬 수 있으며 총감독관과 부감독관이 각 1명씩만 감시할 경우 문제가 된다. 즉, 최대 인원은 1,000,000,000,000 이며 감독관들이 감시할 수 있는 인원이 1명이니, 결과값을 생성했던 result값이 정수형이라면 오버플로우가 발생한다. 즉, long long 형으로 메모리를 늘려주자.  

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
typedef long long ll; 

int main() {


	int n; cin >> n; //강의실 개수 
	vector <int> v(n); 
	for (int i = 0; i < n; i++)cin >> v[i]; 
	int b, c; //총감독관, 부감독관 감시 가능 명수
	cin >> b >> c; 
	ll result = n ;//총감독관 강의실마다 투입 
	for (int i = 0; i < n; i++) {
		v[i] -= b;  //총감독관이 감시할 수 있는 인원 빼기
		if (v[i] <= 0)continue; 
		result += v[i] / c; 
		if (v[i] % c)result += 1; 
	}
	cout << result; 
}

 

13458번: 시험 감독