문제
문제 분석
- 문제를 꼼꼼히 잘 읽고 예외 케이스를 잘 파악해야 되는 문제이다.
- 특히 시험장의 개수가 최대 100만개이고, 각 시험에 있는 응시자 수가 100만명이며, 감독관이 한 시험장에서 감시할 수 있는 수도 모두 1 (B=1, C=1) 이라고 가정했을 때 시간 초과와 자료형에 유의해야 되는 문제이다.
[시간 초과]
- 아래 코드와 같이 while 문을 돌릴 경우, 시험장의 개수가 100만개이고 각 시험에 있는 응시자 수가 100만명이면서, 총감독관, 부감독관 모두 한 시험장에서 감시할 수 있는 응시자의 수가 1명일 때, 최악의 경우 100만 * 100만 번의 연산이 필요하게 된다.
- C++은 1초당 3억~5억번의 연산을 할 수 있고 이 문제의 경우 제한 시간이 2초이므로 적어도 6억번의 연산을 초과하면 안된다. 하지만, 위와 같은 케이스의 연산은 1,000,000,000,000 (1경)번의 연산이 필요하므로 시간 초과가 나오게 된다.
- 따라서 while문 대신, O(1)의 연산으로 해결할 수 있는 방법을 찾아봐야 한다. (정답 코드 참조)
// 총 감독관은 무조건 1명 들어가야 하고, 이후 담당해야 하는 응시자수가 더 있는 경우 부감독관이 최소가 되도록 들어가게 한다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> A;
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int N; // 시험장의 개수
cin >> N;
// 각 시험장에 있는 응시자의 수 입력받기
for (int i = 0; i < N; i++) {
int test_people_num;
cin >> test_people_num;
A.push_back(test_people_num);
}
// 필요한 감독관의 수 세기
int B; // 총 감독관이 감시할 수 있는 사람의 최대 수
int C; // 부 감독관이 감시할 수 있는 사람의 최대 수
cin >> B >> C;
int ans = 0; // 필요한 감독관의 수
for (int i = 0; i < N; i++) {
// 총감독관은 각각의 시험장에 무조건 1명 있어야 한다.
A[i] -= B;
ans++;
// 부감독관을 필요한 만큼 배치한다.(최소)
while (A[i] > 0) {
A[i] -= C;
ans++;
}
}
cout << ans; // 최종 정답 출력
return 0;
}
[자료형]
- 시험장의 개수가 100만개이고 각 시험에 있는 응시자 수가 100만명이면서, 총감독관, 부감독관 모두 한 시험장에서 감시할 수 있는 응시자의 수가 1명일 때, 최악의 경우 필요한 감독관의 수의 최솟값은 1,000,000,000,000 (1경) 이 된다.
- int 형의 범위는 약 21억 이므로, int 자료형을 쓰게 되면 오답처리 된다. 따라서 필요한 감독관의 수를 담는 변수는 long long 자료형을 사용해야 한다.
정답 코드
// 풀이 시간 : 10분 38초 (시간 초과)
// 풀이 시간 : 42분 12초
// 오답노트 : 최악의 경우 정답은 100만개의 강의실 수에 100만개의 응시자 수가 주어질 수 있으므로 while문으로 빼주는 방식은 시간 초과가 발생한다.
// 오답노트 : 최악의 경우 정답은 100만개의 강의실 수에 100만개의 응시자 수가 주어질 수 있고 그러면 정답은 100만*100만이므로 int형 범위를 넘어간다.
// 총 감독관은 무조건 1명 들어가야 하고, 이후 담당해야 하는 응시자수가 더 있는 경우 부감독관이 최소가 되도록 들어가게 한다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> A;
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int N; // 시험장의 개수
cin >> N;
// 각 시험장에 있는 응시자의 수 입력받기
for (int i = 0; i < N; i++) {
int test_people_num;
cin >> test_people_num;
A.push_back(test_people_num);
}
// 필요한 감독관의 수 세기
int B; // 총 감독관이 감시할 수 있는 사람의 최대 수
int C; // 부 감독관이 감시할 수 있는 사람의 최대 수
cin >> B >> C;
long long ans = 0; // 필요한 감독관의 수
for (int i = 0; i < N; i++) {
// 총감독관은 시험장에 1명만 존재해야 한다.
A[i] -= B;
ans++;
// 부감독관을 필요한 만큼 배치한다.(최소)
if (A[i] <= 0) continue; // 총감독관 혼자서 모두 커버 가능
else if (A[i] % C == 0) { // 딱 나눠 떨어지는 경우 ex) 4/2 = 2
ans = ans + (A[i] / C);
}
else { // 딱 나눠 떨어지지 않는 경우 ex) 5/2 = 2 (int/int이므로) , 근데 인원수는 최소 3명 필요하므로 +1
ans = ans + (A[i] / C);
ans++;
}
}
cout << ans; // 최종 정답 출력
return 0;
}
교훈점
- 문제의 조건을 잘 읽고, 자료형과 시간 복잡도를 줄일 수 있는 방법에 대해 고안하는 습관을 길러야겠다.
- 항상 print 문을 찍어보면서 확인하는 습관을 길러야겠다.
