알고리즘(C++) / 백준 13458 : 시험 감독

13458

www.acmicpc.net/problem/13458

13458번: 시험 감독

 

문제

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

 

출력

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

 

코드

//13458 시험 감독
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N;
	vector<int> A;
	int B, C;

	cin >> N;
	
	int a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		A.push_back(a);
	}
	cin >> B >> C;

	long long int people = 0;

	for (int i = 0; i < N; i++) {
		A[i] -= B;
		people++;

		if (A[i] > 0) {
			people += A[i] / C;

			if (A[i] % C != 0)
				people++;
		}
	}

	cout << people << endl;
	
	return 0;
}

 

 

설명

vector A에 응시자 수를 저장하고, B에는 총감독관이 한시험장에서 감시할 수 있는 응시자 수, C에는 부감독관이 한 시험장에서 감시할 수 있는 응시자 수를 저장한다.

한 시험장에서 총감독관이 감시할 수 있는 응시자 수 B를 빼준 후 나머지 응시자를 부감독관이 감독해야한다. C로 나눠주어 몫을 저장하고, 나머지가 존재한다면 감독관의 수가 한 명 더 늘어나야한다. 

 

이때 중요한 것이 출력하는 감독관의 수 people 변수를 long long int형으로 선언해주어야한다.

long long int형의 범위는 [ –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 ] 이와 같다. 이번 문제에서는 출력의 범위가 int형의 범위를 초과하기 때문에 long long 형으로 선언해주어야 한다.

 

 

결과

 

고찰

쉽게 문제를 풀 수 있었다. 하지만 답을 제출했을 때 계속 틀렸다. 그 이유가 감독관의 수를 long long형으로 선언을 해주지 않아서 였다. 여기서 나올 수 있는 최대 감독관의 수는 N과 Ai가 최대이고 B,C가 최소일 때이다. 이때 감독관의 수는 int형의 범위를 초과한다.

결론은 범위를 잘 확인하고 변수를 선언해 주어야한다.