[백준 13458, Java] 시험 감독

문제

www.acmicpc.net/problem/13458

13458번: 시험 감독

 

풀이

 우선 필요한 감독관 수는 N명이다. 왜냐하면 각 시험장에 총감독관 1명이 있어야 하기 때문이다. 그러면 이제 총 감독관이 커버할 수 있는 인원을 제외한 나머지 인원에 대해서 몇명의 부감독관이 필요한지를 생각하면 된다.  다시말해 i번째 시험장에 10명이 있고 총 감독관이 커버할 수 있는 인원이 3명이라고 한다면 10명에서 3명을 제외한 7명에 대해서 몇명의 부감독관이 필요한지를 계산해야한다. 

 

 나머지 정리를 이용하면 된다. 위의 예에서 부감독관이 커버할 수 있는 인원이 3명이라고 한다면 7명에 대해 필요한 부감독관의 수는 3명이다. 3/3/1 인데 이를 수식으로 나타내면 7/3 + (7%3 !=0 이면 +1, 아니면 +0) 으로 나타낼 수 있다.

 

 이때 주의해야할 사항은 결과값이 long이어야 한다는 거다. N= 1,000,000 이고 A = 1, B=1 인경우 필요한 최소 감독관의 수는 1,000,000 * 1,000,000인데 이 값은 int를 넘어가기 때문이다. 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int N;
		int B;
		int C;
		long[] numberOfApplier;		//각 고사장 응시인원	
		long[] numberOfSub;			//총감독관이 커버하고 남은 응시인원수 
		long headCover;				//총감독관이 커버할 수 있는 응시인원 수 
		long subCover;				//부감독관이 커버할 수 있는 응시인원 수 
		long numberOfSupervisor;		//필요한 최소 감독관 수 
		
		
		//입력 
		N = Integer.parseInt(br.readLine());
		numberOfApplier = new long[N];
		numberOfSub = new long[N];
		
		st = new StringTokenizer(br.readLine()," ");
		for(int index = 0; index<N; index++) {
			numberOfApplier[index] = Long.parseLong(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine()," ");
		B = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		headCover = B;
		subCover = C;
		numberOfSupervisor = N;
		
		//계산 
		for(int index =0; index<N; index++) {
			numberOfSub[index] = numberOfApplier[index] - headCover<=0? 0 : numberOfApplier[index] - headCover;
			
			numberOfSupervisor += numberOfSub[index]/subCover;
			if(numberOfSub[index]%subCover!=0) {
				++numberOfSupervisor;
			}
		}
		
		bw.write(String.valueOf(numberOfSupervisor));
		bw.flush();

	}

}