[백준][13458][Java] 시험 감독

www.acmicpc.net/problem/13458

13458번: 시험 감독

문제풀이

시험장, 응시자 수, 감독관이 감시할 수 있는 응시자 수가 1,000,000 이하이어서 시간 초과가 날 수 있기 때문에

수학적으로 접근해야 된다. 무조건 총감독관은 하나씩 배치해야 되며 부 감독관은 남은 응시자를 나누어 더해주고,

정확히 안 나누어 떨어진다면 응시자들을 감시하기 위해 부감독관을 하나 더 배치해야 된다.

여기서 주의할 사항은 시험장 1,000,000에 응시자 수 1,000,000인데 감독관들이 1,1 이 되어 버린다면 필요한 감독관 수가 O(N^2)가 되어 버리기 때문에 변수가 long 이어야 된다.

코드

import java.io.*;
import java.util.*;

public class Main{
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int[] map = new int[N];
		for(int i=0; i<N; i++) {
			map[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		int B = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		
		//총 감독관 배치
		for(int i=0; i<N; i++) {
			map[i] -= B;
		}
		
		long index = N;
		
		for(int i=0; i<N; i++) {
			if(map[i] <= 0) continue;
			
			index += map[i]/C;
			if(map[i] % C !=0) index++;
		}
		
		System.out.println(index);
	}
}