[백준] 13458번 시험 감독(Java)

1) 생각

시험 장의 수와 각 시험장의 인원 그리고 대표감독이 관리할 수 있는 학생수 B와 부 감독이 관리 할 수 있는 학생수 C를 준다. 대표감독은 각 시험장마다 1명만 있을 수 있고 부 감독은 여러명 있을 수 있다. 이때 필요한 최소의 감독수를 구하여라.

처음 생각

백준에 있는 삼성 SW 역량 테스트 기출문제이다. 정답 비율이 23%인데 풀고나니 왜 23%인지를 잘 모르겠다.

▶ 범위가 문제였다고해도 50%는 거뜬히 넘어야 될 것같다. 백준 서버에서 잠시동안 채점 오류가 있었던게 아닌지 조심스럽게 생각해본다.

다음 생각

대표감독은 1명 있을 수 있고 부 감독은 여러명 있을 수 있다. 대표 감독은 무조건 있어야 하므로 무조건 처음에 계산을 해준다.

다다음 생각

대표 감독이 처리할 수 있는 학생수를 제외하고 나서 0명 이하인지를 확인한다. 0명 이하라면 부감독이 있을 필요가 없으므로 다음 시험장으로 넘어간다. 

▶만약 학생들이 남아있다면 부감독은 여러명 있을 수 있으므로 남은 학생을 부감독이 관리할 수 있는 학생수인 C로 나머지 연산을 진행해본다. 나머지가 0이라면 딱 맞아 떨어지므로 남은학생수/C의 수만큼 최소 감독수를 늘려준다.

▶만약 나머지가 0이 아니라면 (남은학생 수/C) +1 만큼 최소 감독수를 늘려준다.

2) 방안

1) 시험장의 개수가 최대 1,000,000이고 학생수도 시험장당 최대 1,000,000이므로 최악의 경우 백만 * 백만 = 1조 이므로 최소 감독수 결과값을 int형이 아닌 long 형으로 선언해 주었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int n,B,C;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        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());
        B = Integer.parseInt(st.nextToken()); // 총 감독관 관리가능 수(한 명)
        C = Integer.parseInt(st.nextToken()); // 부 감독관 관리가능 수(여러 명)
        System.out.println(solve());
    }
    
    private static long solve() {
        long result = 0;
        for(int i=0;i<n;i++) {
            // 총 시험 감독관 집어 넣기.
            int t = arr[i]-B;
            result++;
            if(t<=0) continue;
            // 부 감독관 넣기.
            // 1. 부 감독관이 딱 맞출 수 있냐, 2. 남을 경우 1명더 넣자.
            if(t%C==0) {
                result += t/C;
            }else {
                result += t/C;
                result++;
            }            
        }
        return result;
    }
}