[BOJ] 13458 시험감독 - Java

https://www.acmicpc.net/problem/13458

13458번: 시험 감독

---

1. 문제

브론즈2

시험장 N개, 응시자 수 차례로 주어짐, 총감독관이 감시할 수 있는 응시자 수 B명, 부감독관이 감시할 수 있는 응시자수 C명이 주어질 때

필요한 총감독관과 부감독관의 최소 인원 수를 출력한다.

 

2. 풀이

여기서 총감독관은 반드시 1명 이상 존재, 부감독관은 존재하지 않을 수도 있다.

1 ≤ N ≤ 1,000,000

1 ≤ B, C ≤ 1,000,000

 

핵심은 2가지이다. (나는 이 2가지 핵심 모두 놓쳐서 문제를 푸는데 이틀이 걸렸다..)

1. 예를 들어 N은 1,000,000이고 B, C가 1일 때, ans는 1,000,000 * 1,000,000으로 int 최대 크기를 넘어가게 된다. 때문에 ans는 long 타입이어야 한다.

2. 음수 / 양수 = 음수 가 나올 수 있다. 예를 들어, -5 / 3 = -1이다. 때문에 음수면 반복문을 continue하는 validation check가 필요하다.

 

3. 코드

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

public class Main {
    static int N, B, C;
    static long ans;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        //입력 끝

        ans = N;
        for (int i=0; i<N; i++) {
            arr[i] -= B;
            if (arr[i] < 0) continue;  //핵심 : -5/3 = -1이다.
            ans += arr[i] / C;
            if (arr[i] % C > 0) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

4. 사담

답을 보면 재미가 없어진다.

문제랑 싸워서 누가 이기나 해보자 ..