백준 13458번 [시험 감독](C++) -yes6686- 티스토리

백준 문제 풀이: 13458 (시험 감독)

---

문제 링크: https://www.acmicpc.net/problem/13458

문제 설명:

각 시험장에는 총감독관과 부감독관이 필요합니다. - **총감독관**은 반드시 1명만 있어야 하며, 시험장에 있는 모든 학생을 감독합니다. - **부감독관**은 여러 명 있을 수 있지만, **한 명당 최대 c명**의 학생만 감독할 수 있습니다.
각 시험장의 학생 수가 주어졌을 때, 모든 학생을 감독하기 위해 필요한 감독관의 **최소 인원**을 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1000001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 시험장의 수
    cin >> n;

    // 각 시험장의 학생 수 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int b, c; // 총감독관과 부감독관이 감시할 수 있는 학생 수
    cin >> b >> c;

    long long int minAns = 0; // 필요한 감독관 수 (long long 사용)

    for (int i = 0; i < n; i++) {
        arr[i] -= b; // 총감독관이 감시 가능한 학생 수만큼 제외
        minAns += 1; // 총감독관 1명 추가

        if (arr[i] > 0) { // 남은 학생 수에 대해 부감독관 계산
            minAns += arr[i] / c; // 부감독관이 필요한 수
            if (arr[i] % c != 0) { 
                minAns += 1; // 남은 학생이 있으면 부감독관 1명 추가
            }
        }
    }

    cout << minAns; // 필요한 감독관의 최소 수 출력
}

---

코드 설명

• 총감독관 처리: - 각 시험장에 총감독관 1명은 반드시 필요하므로, 먼저 `1명`을 추가합니다.
• 학생 수 차감: - 총감독관이 감시할 수 있는 `b`명을 제외하고 남은 학생 수를 계산합니다.
• 부감독관 처리: - 남은 학생 수를 `c`로 나눈 몫만큼 부감독관을 추가합니다. - 나머지가 존재하면 부감독관을 1명 더 추가합니다.
• 시간 복잡도: - 각 시험장을 한 번씩 순회하므로 시간 복잡도는 **O(n)**입니다.

---

입출력 예시

• 입력 예시:

  5  
  10 9 10 9 10  
  7 2

• 출력 예시:

  13

---

결론

이 문제는 각 시험장에 대해 **총감독관**과 **부감독관**을 나누어 배치하는 단순한 반복문 문제입니다. 총감독관 1명은 무조건 필요하고, 남은 학생 수를 부감독관이 나누어 맡는 방식을 반복해서 구합니다. 시간 복잡도가 **O(n)**이기 때문에 입력 크기가 커도 효율적으로 해결할 수 있습니다.