백준 13458번. 시험 감독 (Java, Python)

Problem

• 문제 링크

각 시험장의 응시생을 모두 감독하기 위해 필요한 감독관의 최소값을 구하는 문제입니다.

Solution

Greedy 문제입니다.

각 방마다 총 감독관은 꼭 한명씩 있어야 하기 때문에 빼줍니다.

만약 총감독관 - 감시 학생 수 > 0 이라면 부감독관이 필요하다는 뜻입니다.

부감독관은 남은 학생 수 / 부감독관의 감시 학생 수 만큼 필요합니다.

만약 딱 나누어 떨어지지 않는 경우 부감독관이 한명 더 필요합니다.

그래서 남은 학생 수 % 부감독관의 감시 학생 수 != 0 라면 부감독관을 한명 더 추가해주어야 합니다.

나머지가 0 으로 딱 나누어 떨어진다면 추가할 필요가 없습니다.

간단한 문제이지만 많이 틀리는 이유는 자료형 때문이라고 생각합니다.

100만개의 시험장에 100만명의 학생들이 들어가있는데 총감독관과 부감독관이 감시하는 학생 수가 1명밖에 안된다면

총 감독관은 100만 * 100만 만큼 필요하게 됩니다.

int 형으로는 커버할 수 없으므로 total 변수를 long으로 선언해줍니다.

파이썬은 해당되지 않습니다. 그냥 계산해주시면 됩니다.

Java Code

import java.util.*;
import java.io.*;
 
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
 
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
 
        st = new StringTokenizer(br.readLine());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
 
        long total = n;
        for (int i=0; i<n; i++) {
            // 총감독관은 무조건 한명씩 필요
            a[i] -= b;
 
            // 부감독관으로 나머지 채우기
            if (a[i] > 0) {
                total += a[i]/c;
 
                if(a[i] % c != 0) {
                    total++;
                }
            }
        }
 
        System.out.println(total);
    }
}

Python Code

# -*- coding: utf-8 -*-
 
import sys
 
N = B = C = 0
 
def solve(A):
    count = 0
 
    for i in range(N):
        ## 각 반에서 총 감독관은 한명씩 필요
        if A[i] > 0:
            A[i] -= B
            count += 1
        
        ## 나머지 부감독관으로 채우기
        if A[i] > 0:
            count += int(A[i]/C)
 
            if A[i] % C != 0:
                count += 1
 
    return count
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    B, C = map(int, sys.stdin.readline().split())
 
    result = solve(A)
    print(result)