백준 13458 시험 감독 C++

문제

총 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)

출력

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

 

풀이

총 부

C B

1 ??

 

한 시험장에서

1)총감독관이 감시 가능한 사람 수보다 응시자 수가 작거나 같을 경우 → 1명

2)총감독관이 감시 가능한 사람 수보다 응시자 수가 큰 경우 →

i) (총감독관이 감시 불가능한 사람의 수 / 부감독관이 감시가능한 수)가 나누어 떨어진 경우 →

 총감독관의 수(1명) + 부감독관의 수(총감독관이 감시 불가능한 사람의 수 / 부감독관이 감시가능한 수)  

ex) 총 감독관: 5명 부감독관은 3명이 가능하면

11명의 강의실이면 5+ 3+ 3

                           1 + 2 = 1 + (11-5)/3 = 3

ii)(총감독관이 감시 불가능한 사람의 수 / 부감독관이 감시가능한 수)가 나누어 떨어지지 않은 경우→

나누어 떨어지지 않은 나머지 사람들도 감독하는 사람이 있어야 한다.

총감독관의 수(1명) + 부감독관의 수(총감독관이 감시 불가능한 사람의 수 / 부감독관이 감시가능한 수 + 1)

ex) 총 감독관: 5명 부감독관은 3명이 가능하면

10명의 강의실이면 5+ 3+ 2

                           1 + 2 = 1 + (10-5)/3  + 1= 3

근데 처음 풀이 결과 틀렸다.

왜냐하면 ans의 범위를 Int라고 했는데 int의 범위를 초과했기 때문이다.

long long int ans = 0;

범위 유의하자

 

#include <iostream>
using namespace std;
#define MAX 1000000
int a[MAX];
int s[MAX];

int main() {
	int n, b, c;
	
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	cin >> b >> c;

	int ans = 0; 
  //long long int ans = 0;//범위 유의하자

	for (int i = 0; i < n; i++) {
		if (a[i] - b <= 0) {
			//총감독관이 감시 가능한 사람 수보다 응시자 수가 작거나 같을 경우
			s[i] = 1;
		}
		else {
			//총감독관이 감시 가능한 사람 수보다 응시자 수가 큰 경우
			if ((a[i] - b) % c == 0) {
				s[i] = 1 + (a[i] - b) / c;
			}
			else {
				s[i] = 1 + (a[i] - b) / c + 1;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		ans += s[i];
	}

	cout << ans;

}