[java,백준13458]시험 감독 - 수학적 접근

각 시험장별 필요한 감독관 수를 계산하여 최소 감독관 수를 구하는 수학적 접근 문제입니다.

시험 감독(백준13458)


예시 시각화:

N = 5 (시험장 수)
응시자 수: 10 9 10 9 10
B = 7 (총감독관 감시 인원)
C = 2 (부감독관 감시 인원)

시험장별 감독관 배치 과정:
1번 시험장(10명 응시자) → 총감독관1명 (7명 응시자) + 부감독관2명 (4명 응시자) = 3명 필요
┌─────────┐
│ 👥👥👥👥👥 │ 
│ 👥👥👥👥👥 │ 
│ 👨‍1(총감) 👨‍2(부감) │
└─────────┘

2번 시험장(9명 응시자) → 총감독관1명 (7명 응시자) + 부감독관1명 (2명 응시자) = 2명 필요
┌─────────┐
│ 👥👥👥👥  │ 
│ 👥👥👥👥👥 │ 
│ 👨‍1(총감) 👨‍1(부감) │
└─────────┘

...이하 동일한 방식으로 계산



풀이

구현 시 주의사항

💡 단순해 보이는 문제지만 오버플로우 처리가 매우 중요! (long 사용하자)
입력값이 큰 경우 int 범위를 벗어날 수 있기 때문! (실제로 벗어난다!)

💡 총감독관 1명을 먼저 배치한 후, 부감독관을 필요한 만큼 추가하는 방식으로 구현 (수학적 계산)


핵심 구현 사항

  • long 자료형 사용 필수
    • B,C가 1이고 N,A가 백만인 경우 백만*백만으로 int범위를 벗어남
  • 총감독관은 반드시 1명씩 배치
    • 문제의 요구사항임
  • 부감독관은 남은 인원에 따라 계산


총감독관 배치

for (int i = 0; i < N; i++) {
    input[i] -= B;
    result++;
    if(input[i] < 0) input[i] = 0;
}


부감독관 배치

for (int i = 0; i < N; i++) {
    if (input[i] % C == 0) {
        result += input[i]/C;
    } else {
        result += (input[i]/C + 1); //수학적으로 나머지 있을 때 +1 요함
    }
}



전체 코드

public class 시험감독_13458 {
    static int N, B, C;
    static int[] input;
    static long result;

    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.println(result);
    }

    private static void solve() {
        result = 0;
        for (int i = 0; i < N; i++) {
            input[i] -= B;
            result++;
            if(input[i] < 0) input[i] = 0;
        }
        for (int i = 0; i < N; i++) {
            if (input[i] % C == 0) {
                result += input[i]/C;
            } else {
                result += (input[i]/C + 1);
            }
        }
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        input = new int[N + 1];
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(stk.nextToken());
        }
        stk = new StringTokenizer(br.readLine(), " ");
        B = Integer.parseInt(stk.nextToken());
        C = Integer.parseInt(stk.nextToken());
    }
}

주관적인 생각의 풀이이므로 틀린 부분 지적은 언제나 환영합니다⚡

댓글남기기

참고