문제 설명

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

---

나의 풀이

import java.util.Scanner;

public class TestMngr {

	public static void main(String[] args) throws Exception {
		
        // 최소 감독관 수
		long answer = 0;
		
		Scanner sc = new Scanner(System.in);
		
		// 전체 시험장 수
		int totRoomCnt = sc.nextInt();
		
		// 각 시험장별 응시자 수
		int[] roomArr = new int[totRoomCnt];
		for (int i = 0; i < roomArr.length; i++) {
			roomArr[i] = sc.nextInt();
		}
        
        // 감독관별 학생 수 (총감독관, 부감독관)
		int masterMngrCnt = sc.nextInt();
		int subMngrCnt = sc.nextInt();
		
		for (int i = 0; i < roomArr.length; i++) {
			
            // 각 시험장마다 총감독관 1명이 필요하므로
            roomArr[i] -= masterMngrCnt;
			answer++;
			
			if (roomArr[i] > 0) {
				answer += roomArr[i]/subMngrCnt;
                if (roomArr[i]%subMngrCnt > 0) {
                	answer++;
                }
			}
		}
		
		System.out.print("최소 감독관 수 : " + answer);
	}
}

---

풀이포인트

1. 삼성 SW 역량 테스트 기출문제

2. 이 문제에 탐욕법이 적용 가능한 것은, 각 시험장의 최소 감독관의 수를 구하면 결국 전체를 감독하기 위한 감독관의 수를 구할 수 있기 때문에 단계별로 도출된 값이 최적의 해가 되기 때문이다. 또한 총감독관의 수와 부감독관의 수를 구하는 부분이 독립적이기 때문에 탐욕법으로 접근이 가능하다.

3. 문제풀이 방식을 생각하는 데에 시간이 꽤 걸렸으나 구현 자체는 간단했다.

4. 최소 감독관 수의 자료형은 long으로 지정해줘야 한다. 알고리즘은 맞게 구현하였으나 계속 오류가 나서 다른 사람의 풀이를 참고한 결과 시험장의 수가 백만 개, 각 시험장의 응시자 수가 백만 명, 각 감독관이 감독할 수 있는 최소 학생 수가 1일 경우 필요한 최소 감독관의 수는 백만 X 백만 으로 int 형의 범위를 초과하기 때문이다.