예제: 시험 감독
문제
총 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)
출력
각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.예제 입력 1
1 1 1 1예제 출력 1
1예제 입력 2
5 1000000 1000000 1000000 1000000 1000000 5 7예제 출력 2
714290예제 입력 3
5 10 9 10 9 10 7 2예제 출력 3
13
풀이
필자 기준으로 문제는 이해하기 쉬웠고, 풀어봤던 다른 삼성 기출문제에 비해 쉬운 난이도 였다.
반올림((수험생수 - 총감독관 감독수) / 부감독관 감독수)을 구하여 더하면 되었기 때문이다.
하지만 함정이 있다. 그것은 바로 자료형!!
답은 int로 return하면 틀린다. 힌트는 시험장의 개수와 응시자의 수를 보면, 답이 최대일 때 int의 자료형 범위를 넘어버린다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int N, A, B, C;
vector<int> nums;
int main() {
long res = 0;
cin >> N;
nums = vector<int>(N, 0);
for (int i = 0; i < N; i++) {
cin >> nums[i];
}
cin >> B >> C;
for (int i = 0; i < N; i++) {
nums[i] = (nums[i] - B >= 0 ? nums[i] - B : 0);
}
res += N;
for (int i = 0; i < N; i++) {
double div = ceil((double)nums[i] / C);
res += div;
}
cout << res << endl;
return 0;
}풀이 후기
실전이었으면 필자도 바로 탈락이었을 문제였다. 알고리즘 자체는 쉬웠지만, 자료형을 쉽게 생각하지 않기 때문에 한 번 틀리고 말았다. 진짜 삼성문제는 방심하지 않고 꼼꼼히 읽어야만 풀 수 있는 문제인 것 같다.
