[BF] 13458번 시험 감독

13458번 시험 감독

 

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

 

문제

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 방에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 방에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

 

출력

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

 

예제 입력

1
1
1 1

3
3 4 5
2 2

5
1000000 1000000 1000000 1000000 1000000
5 7

5
10 9 10 9 10
7 20

5
10 9 10 9 10
7 2

 

예제 출력

1

7

714290

10

13

 

해결방법

1) 시간초과

• 먼저 n만큼 반복하여 총감독관의 감시만큼 뺀다. 그리고 다시 n만큼 반복하여 부감독관의 감시를 빼며 반복문을 돌린다
• 이는 n=1,000,000 인 것을 감안했을 때, 시간초과가 발생한다

 

2) 63%시간초과

• n만큼 반복하면서 총감독관의 감시만큼 빼고, 만약 남은 인원이 0보다 크다면 부감독관의 감시만큼 반복하여 인원을 뺀다
• 이 또한, 시간초과가 발생했는데 부감독관의 감시만큼 뺄 때, 반복문을 사용하면 안되는 것 같다

 

3) 틀렸습니다

• n만큼 반복하면서 총감독관의 감시만큼 빼고, 만약 남은 인원이 0보다 크다면
• 남은 인원 / 부감독관 감시 + 1
• 을 하여 ans에 더해준다
• 이는 시간초과는 해결했지만 결과가 나오지 않았다. (아마 반례가 있는듯 하다)

 

4) 맞았습니다!! (⭐️논리를 다른 블로그에서 참고함 ㅜㅜ⭐️)

• n만큼 반복하면서 총감독관의 감시만큼 빼고, 만약 남은 인원이 0보다 크다면
• 두 가지 경우를 조건문으로 나눈다.
• 첫번째는 (남은인원 % 부감독관 감시 == 0) 인경우, 두번째는 나머지가 0이 아닌경우
• 첫번째 경우는 딱 나눠떨어지는 경우이기 때문에 +1을 빼주고, 아닌 경우는 +1을 해주면 되었다.

if(testsite[i] > 0){
    if(testsite[i]%c == 0)
        ans += (testsite[i] / c);
    else
        ans += (testsite[i] / c + 1);
}

 

 

✅ int 와 long long 의 차이점

정수 자료형 int는 32/64비트 환경에 상관없이 4바이트의 정보를 기록할 수 있는 자료형입니다. signed int(부호가 있는 정수)를 기준으로 기록할 수 있는 양의 정수 범위는 0 ~ 2,147,483,647(16진수로 7FFFFFFF)인데요.

 

파도반 수열을 예로 들면 N = 79부터 이 int로 계산할 수 있는 범위를 넘어서게 됩니다. 이를 산술 넘침 혹은 Overflow라고 하지요. 그래서 4바이트의 저장 공간만으로는 좀 더 큰 정수를 계산할 수 없게 되었고, 점점 커져가는 메모리 공간, 계산량에 어느 정도 대비할 필요가 있게 되었습니다. 따라서 1999년도 C언어 표준안(C99)에서 8바이트의 크기를 가지는 정수 자료형 long long이 소개되었고, C++은 2011년도 C++ 표준안(C++11)에서 이 자료형을 지원하게 되었죠. long long은 8바이트의 공간을 가지는 자료형이기에 signed long long을 기준으로 하면 최대 계산할 수 있는 양의 정수 범위는 0 ~ 9,223,372,036,854,775,807(16진수로 7FFFFFFFFFFFFFFF)가 되어 파도반 수열에서 보였던 문제를 해결할 수 있게 된 것입니다.

 

옆의 링크는 C++11의 long long 자료형에 대한 간단한 Wikipedia 내용인데, 참고하실 일이 있으면 참고해보시길 바랍니다 :) https://en.wikipedia.org/wiki/...

 

주로 int와 long long을 구분하며 사용하실 땐, 주어지는 입력값의 범위를 고려해보시고 그 값이 int로 표현이 불가능한 값이면 long long, long long으로도 불가능하면 BigInteger를 건들면 크게 문제를 해결하는데 애로사항은 없으실 겁니다.

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 100000
#define INF 987654321
using namespace std;

int n;
int a;
int b,c;

int testsite[MAX];

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> testsite[i];
    }
    cin >> b >> c;
    // 수행
    long long ans = 0;
    for(int i=0; i<n; i++){
        testsite[i] -= b;
        ans++;
        
        if(testsite[i] > 0){
            if(testsite[i]%c == 0)
                ans += (testsite[i] / c);
            else
                ans += (testsite[i] / c + 1);
        }
    }
    cout << ans << endl;
}