[백준 알고리즘] 13458 시험 감독

https://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)

출력

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

 

풀이

int형 (4bytes == 32bit) 의 범위 : -2,147,483,648 ~ +2,147,483,647

64bit에서의 long(8bytes == 64bit) 범위 : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 (단 32bit에서의 long 범위는 int와 동일)

 

해당 문제에서 여러번 틀린 이유는 int형의 범위 때문이었다. 통상적으로 알고리즘 문제 풀 때 자료형의 범위 때문에 틀리는 경우가 종종 있는데 이 문제도 그러한 케이스였다.

 

추가로 해당 범위 찾아보다가 extra tip부분을 봤는데

 

Extra)

Visual Studio는 스택 크기를 1MB로 기본 설정하며, 이 크기를 초과하면 스택 오버플로가 발생.

따라서 int형 배열 25만개 이상 만들지 말것. (출처: https://gudwns999.tistory.com/53)

 

참고해두자.

 

이 알고리즘에서 최악의 경우의 수는 시험장의 수가 최대 일 때, 각 시험장의 응시자 수가 최대일 때, 감독관이 감독할 수 있는 응시자가 각각 1명일 때이다.

 

그럴 때 시험장마다 총감독관은 1명, 부 감독관은 10⁶ -1 명 만큼 필요하고 시험장은 10⁶개가 있으므로 곱하게 되면 

10⁶ + 10⁶(10⁶-1) = 10¹²명이 된다. 그렇기 때문에 int 범위가 넘어가므로 long 자료형을 써야한다. 

 

 

#include<iostream>
#include<vector>
#include<math.h>
#include<cmath>

using namespace std;

int main() {


	int testPlace=0;	//시험장의 수
	vector<int> vc; //시험장마다 응시생의 수

	int mainMng = 0; // 총감독이 감독할 수 있는 사람.
	int subMng = 0; //  부감독이 감독할 수 있는 사람.
	long count = 0; // 감독관의 최소 수 

	cin >> testPlace;

	for (int i = 0; i < testPlace; i++) {
		int temp;
		cin >> temp;
		vc.push_back(temp);
	}

	cin >> mainMng >> subMng;
	count += testPlace; //총 감독관은 한명씩 배치되어야 하므로

	for (int j = 0; j < testPlace; j++) {

		int subcount = 0;
		if (vc[j] <= mainMng) {
			continue;
		}
		
		else {
			subcount = ceil((double)(vc[j] - mainMng) / (double)subMng); //올림! #include<cmath.h> 필요
			//cout << "sub " << subcount << endl;
			count += subcount;
		}

		

	}

	cout << count << endl;

	



}

 

끝.