[C++] 백준 13458 시험 감독

www.acmicpc.net/problem/13458

13458번: 시험 감독

 

1. 서론

 

삼성 기출에 있어서 풀었는데 브론즈인데 왜 이렇게 정답률이 낮을까 했는데 그럴만했다. 문제를 푸는 것 자체가 어려운 게 아니라 조건을 맞추는 것이 중요하다는 것을 알려준 문제. 아주 교훈적이다...

내가 얻은 교훈: int, long 등의 범위가 틀려도 시간 초과가 날 수 있다. 그리고 값이 바뀌기 때문에 당연히 틀렸습니다도 나온다...

+ int와 long의 차이는 그 둘의 범위는 같아 보이지만 플랫폼(비트)에 따라 int는 범위가 가변적인 것에 반해 long은 고정적이기 때문에 코드를 돌렸을 때 차이가 나는 것이다. 

 

2. 문제 풀이

 

N개의 시험장이 있고 각 시험장마다 시험 인원이 다르게 있다. 그리고 이들을 감독하는 감독관이 있는데 총감독관과 부감독관이 있다. 총감독관은 1명만 있을 수 있고 부감독관의 인원은 제한이 없다. 문제에서는 정확하게 표현을 안 해줬지만 총 감독관 1명은 꼭 있어야 하는 것을 전제로 풀었다. 총감독관과 부감독관은 각자 감시할 수 있는 인원이 정해져 있는데 이것도 입력으로 주어진다. 이때 최소로 모든 인원을 감독할  수 있는 감독관의 수를 구하는 것이 문제다. 

 

처음에는 단순하게 시험인원에서 총감독관이 감시할 수 있는 인원의 수를 제외하고 나머지를 부감독관이 감독할 수 있는 인원의 수를 빼면서 count를 했는데 그게 시험 인원의 범위(~ 1,000,000)가 크다 보니 시간 초과에 걸리고 말았다.... 어쩐지 이렇게 간단하게 풀 수 있는 문제가 아니겠거니 하고 방법을 바꿨다. n번을 빼는 것은 시간이 너무 오래 걸리니까 나누기와 나머지를 이용했다.

 

만약 시험인원이 100명이 있고 총 감독관은 3명을, 부감독관은 2명을 감시할 수 있다. 이 경우에 97명부터 시작해서 부감독관이 몇 명이 있어야 최소 인원으로 시험을 치를 수 있을까?

97명에서 나누기 2를 한다. 97 /2 = 48. 그리고 나머지가 1이기 때문에 감독관을 한 명 더 추가해준다.

그렇게 되면 총감독관 1명, 부감독관 48 + 1명 해서 최소 50명의 감독관이 필요하게 된다.

나누기와 나머지를 이용하면 직접 빼면서 count 하는 것보다는 훨씬 빨리 계산이 가능하기 때문에 시간 초과에 걸리지 않고 문제를 풀 수 있다.

 

3. 코드 설명

 

#include <cstdio>

using namespace std;

int main()
{
    long a[1000001], n, i, b, c, cnt = 0;

    scanf("%ld", &n);

    for (i = 0; i < n; i++)
        scanf("%ld", &a[i]);

    scanf("%ld %ld", &b, &c);

    for (i = 0; i < n; i++)
    {
        a[i] -= b;
        cnt++;
        while(a[i] > c)
        {
            cnt += a[i] / c;
            a[i] = a[i] % c;
        }
        if (a[i] > 0)
            cnt++;
    }

    printf("%ld\n", cnt);
}

 

원래 백터도 써보고 iostream도 썼는데 시간 초과랑 메모리 때문에 scanf, printf, 배열로 바꿔줬다.

 

값들을 입력받고 총 학생 수에서 총감독관이 감독할 수 있는 인원의 수만큼 빼준다. 그리고 반복문에서 학생수와 부감독관의 감독인원을 나눈 값을 cnt에 더해주고 나머지 값을 학생 값에 저장한다. 나머지가 부감독관이 감독할 수 있는 인원의 수보다 작아지면 반복문을 빠져나온다. 하지만 남은 인원들도 감독을 해줘야 하기 때문에 감독관을 한 명 더 추가해준다. 그리고 출력한다.

이때 모든 숫자들의 최대값이 1,000,000 이기 때문에 long을 써줘야 값이 변하지 않는다. (여기서 int로 고치면 답이 틀렸다고 나옴)