[백준 알고리즘] 백준 13458번 시험 감독 자바 (JAVA)

 

백준 13458번 시험 감독 자바 (JAVA)

1) 문제 번호 : 13458

 

2) 문제 링크 

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

13458번: 시험 감독

 

3) 문제 내용

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

 

4) 제약 사항 : 없음

 

5) 입력

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

 

6) 내 풀이

 

우선 여기서 응시장의 수 즉 N은 필요가 없다고 생각했다. 왜냐하면 두번째 줄에 입력받는 응시자의 수가 공백단위로 주어지기 때문에 split(" ") 함수를 사용하여서 인원들의 수가 담긴 배열을 생성한다. 그리고 세번째 줄에 주어지는 총감독관이 감시할수 있는 수와 부감독관이 감시할수 있는 수를 split으로 뽑아 double형의 실수로 저장해준다. 각각 Main과 Sub라고 칭한다.

 

그 후 loop를 응시자 수 배열만큼 돌면서 응시자의 수(X라고 칭함)에서 Main을 빼준값이 0보다 크거나 같다면 X에서 main을 빼준뒤 카운트를 1증가시킨다.

그후 X가 0보다 크다면 카운트에 Math.max메서드를 이용해서 1과 X/sub를 올림한값을 넣어준다.

 

7) 내 코드

package baekjun.math;

import java.io.*;

public class _13458 {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int count=0;

        String[] chars = br.readLine().split(" ");
        String[] chars2 = br.readLine().split(" ");

        double main = Integer.parseInt(chars2[0]);
        double sub = Integer.parseInt(chars2[1]);

        for (int i=0;i<chars.length;i++){
            double X = Integer.parseInt(chars[i]);
            if(X-main>=0){
                X-=main;
                count++;
            }
            if (X>0){
                count+=Math.max(1,Math.ceil(X/sub));
            }
        }
        System.out.println(count);
    }
}

 

8) 코드 복기

모든 테스트 케이스를 통과했고 루프한번에 조건문이 두개 뿐이라 시간초과도 없이 통과일줄 알았다.

하지만 틀렸다 대체왜?? 런타임도 아니고 시간초과도아닌 그냥 정답이 아니다 분명 테스트케이스를 통과했고 맞는 코드라고생각했는데

이유를 알 수없어서 다른 사람들의 코드를 배우기로했다.

 

9) 정답 및 배운코드

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;

    }

}

 

 

---

로직자체는  내 코드와 유사하지만 나는 결과값을 long으로 설정해주지 않았었고 그렇기 때문에 최악의 경우 시험장의 개수가 최대 1,000,000이고 학생수도 시험장당 최대 1,000,000이므로 최악의 경우 백만 * 백만 = 1조 이므로 에러가 날 수 밖에없었고 맨처음 주어진 N을 쓰지않아 문제가 틀렸었다. 주어진 입력을 모두 사용하여 문제를 풀어야하는 것을 간과한 나의 잘못이었다.