[백준] 13458번: 시험 감독 - java

문제

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

13458번: 시험 감독

 

접근법

쉬운 문제이지만 문제 풀 때 놓치기 쉬운 부분들이 있다. 나 역시 브론즈 주제에 5번이나 제출한게 너무 억울해서 정리해본다..... 알고리즘은 정말 쉬우니 혼자 생각해보길!

 

알고리즘이 맞는거 같음에도 불구하고 초반에 바로 "틀렸습니다"가 뜨는 경우는 long을 사용하지 않아서 틀린 경우가 주로 있다. 이 문제 역시 감독관의 최소 수가 int 범위를 넘어간다. 

 

N = 1,000,000, N개의 시험장의 응시자 수 각 1,000,000명, B와 C가 둘 다 1이라고 할 때

각 시험장에 필요한 감독관은 1,000,000명이기 때문에 총 $1,000,000 * 1,000,000 = 10^{12}$ 명의 감독관이 필요하게 된다.

따라서 감독관의 수는 int 타입이 아닌 long 타입으로 선언해야 한다.

 

그리고 나는 모든 시험장에서 총감독관은 무조건 한 명은 있어야 되기 때문에 각 시험장에서 총감독관이 감시할 수 있는 인원(B)는 빼고, 나머지를 C로 나눈 뒤 올림 연산을 해 답을 구했었다. 이때 간과했던 점이 있었는데, 바로 B를 뺐을 때 그 값이 마이너스가 될 수도 있다는 점이였다. 즉, 총감독관이 감시할 수 있는 인원이 응시자 수 보다 클 수 있다는 것이였다. 이 부분은 Math.max(0, ...)을 사용해 수정하였다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, B, C;
    static int[] A;
    static long answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        A = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        answer = N; // 총 감독관 수
        for (int i = 0; i < N; i++) {
            long tmp = (long)Math.ceil((double)(A[i] - B) / C);
            answer += Math.max(tmp, 0);
        }

        System.out.println(answer);
    }
}