문제
N개의 시험장이 있고, 각 시험장에 응시자 수가 주어진다. 각 시험장에 총감독관 1명을 반드시 배치해야 하며, 총감독관은 B명을 감독할 수 있다. 부감독관은 C명을 감독할 수 있다. 모든 응시자를 감독하기 위해 필요한 최소 감독관 수를 구하는 문제다.
입력
- 첫째 줄: 시험장 수 N (1 ≤ N ≤ 1,000,000)
- 둘째 줄: 각 시험장의 응시자 수 (1 ≤ Ai ≤ 1,000,000)
- 셋째 줄: B, C (총감독관 감독 인원, 부감독관 감독 인원)
출력
필요한 최소 감독관 수 (int 범위 초과 가능하므로 long 사용)
예제
| 입력 | 출력 |
|---|---|
1 1 1 1 | 1 |
3 3 4 5 2 2 | 7 |
풀이
각 시험장마다 총감독관 1명을 우선 배치하고, 남은 응시자를 부감독관으로 채운다. 나눗셈의 올림 처리를 이용해 필요한 부감독관 수를 계산한다.
- N개의 시험장을 순회하며 총감독관 1명씩 배치하고, 해당 시험장 응시자를 B만큼 감소시킨다.
- 남은 응시자가 있으면
(남은 인원 + C - 1) / C(올림 나눗셈)으로 부감독관 수를 계산한다. - 답이 int 범위를 초과할 수 있으므로
long타입을 사용한다.
핵심 아이디어: 총감독관은 시험장당 반드시 1명이므로 기본 N명에서 시작한다. 나머지 응시자는 (arr[i] % C == 0) ? arr[i] / C : arr[i] / C + 1 로 부감독관 수를 올림 계산한다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day37BOJ13458시험감독 { // 13458 시험감독
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
long ans = 0;
for (int i = 0; i < N; i++) {
ans++;
if (arr[i] > B) {
arr[i] -= B;
ans += (arr[i] % C == 0) ? arr[i] / C : arr[i] / C + 1;
}
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(N) — N개의 시험장을 한 번 순회
- 공간: O(N) — 응시자 수 배열 저장