[백준 13458번] - 시험감독

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

 

[문제 설명]

 

---

[문제 풀이]

- 문제 이해
시험장이 N개 있고, 각 시험장에는 특정 수의 응시생들이 있습니다. 총감독관은 한 시험장에서 B명까지, 부감독관은 C명까지 감시할 수 있습니다. 모든 응시생을 감시하기 위해 필요한 최소 감독관 수를 구하는 문제입니다.

- 제약 조건
시험장 개수 N: 1 ≤ N ≤ 1,000,000

응시생 수: 1 ≤ A[i] ≤ 1,000,000

감시 가능 인원: 1 ≤ B, C ≤ 1,000,000

- 접근 방법

1. 총감독관은 반드시 1명: 각 시험장에는 최소 1명의 총감독관이 필요합니다.

2. 부감독관은 여러 명: 남은 인원에 따라 여러 명의 부감독관이 필요할 수 있습니다.

3. 큰 수 처리: N과 A[i]가 최대 1,000,000이므로 결과값이 int 범위를 넘을 수 있습니다

핵심 아이디어

각 시험장 i에 대해:
총감독관 1명 필수 배치
남은 인원 = A[i] - B
만약 남은 인원이 0보다 크다면, 부감독관 수 = (남은인원 + C -1)/ C (올림처리)

 

[코드]

[GitHub]

https://github.com/EGyeom/ProblemSolving/commit/534f322cc3d0671bb4fea71ff8d4ea5a414d3dad

#include <stdio.h>

int main()
{
    int n, b, c;
    long long answer = 0; // 오버플로우 방지를 위해 long long
    int a[1000000];
    
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    scanf("%d %d", &b, &c);
    
    for(int i = 0; i < n; i++)
    {
        // 총감독관 1명 무조건 배치
        answer++;
        
        // 부감독관 계산
        int remain = a[i] - b;
        if(remain > 0)
        {
            answer += (remain + c - 1) / c; // 올림 계산
        }
    }
    
    printf("%lld\n", answer);
    return 0;
}