[Java] 13458. 시험 감독

www.acmicpc.net/problem/13458

13458번: 시험 감독

N개의 시험장과 각 시험장의 A만큼의 응시자가 있다.

감독관은 총감독관과 부감독관으로 나뉘는데, 각 감독관마다의 감시할 수 있는 응시자의 수인 B, C가 주어진다.

 

각 응시장에는 총감독관 1명이 필수로 있어야 하고, 부감독관은 여러명 있어도 된다.

주어진 입력값을 이용하여 감독관의 최솟값을 구하는 것이 문제이다.

 

문제에 접근하는 방법은 다음과 같았다.

 

1. N 변수에 고사장의 수를 입력받는다.

2. A 배열에 각 고사장마다의 응시자 수를 입력받는다.

3. B, C로 총감독관과 부감독관이 감시할 수 있는 수를 입력받는다.

4. A의 배열을 순회하면서 총감독관이 감시할 수 있는 인원 수인 B를 각각 빼고, 감독관의 수를 증가시킨다.

5. 남은 A를 다시 순회하면서 부감독관이 감시할 수 있는 수인 C로 나눴을 때의 나머지가 0이면 남은 인원이 없는 것으로 간주하고 A/C만큼을 부감독관의 수로 더해주고, 만약 나머지가 0이 아니라면 남은 응시자가 존재한다는 의미이기 때문에 A/C+1을 감독관의 수에 더해주게된다.

---

이 문제를 풀면서의 핵심은 결과값의 타입이다.

 

이 문제에서 대부분 저지를 수 있는 실수는 int type으로의 선언일 것이다.

 

이 시점에서 입력값의 범위를 다시 확인해보면 시험장의 개수는 100만개, 각 응시장의 최대인원도 100만명이다.

따라서 총감독관과 부감독관이 감시할 수 있는 인원이 각 1명씩이라면 100만 * 100만이 결과값으로 나올 수 있는 최대값이라고 할 수 있다. 100만 * 100만은 조 단위이기 때문에 int형의 표현범위인 2^16보다 큰 수를 갖게 된다.

 

따라서 결과값의 타입을 long형으로 선언해주는 것이 바람직하다고 할 수 있다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < A.length; i++) {
			A[i] = sc.nextInt();
		}
		int B = sc.nextInt();
		int C = sc.nextInt();
        
		//1
		long cnt = 0;		
        
		//2
		for (int i = 0; i < A.length; i++) {
			A[i] -= B;
			cnt++;
		}
        
		//3
		for(int i : A) {
			if(i>0) {
				if(i%C != 0)
					cnt += (i/C) + 1;
				else
					cnt += (i/C);
			}
		}
		System.out.println(cnt);
		sc.close();
	}

}