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

🔗 문제

13458번: 시험 감독

13458번: 시험 감독

 

🖍 풀이

 

총감독은 필수이기 때문에 최소 N명의 감독님.

그리고 우리가 구할 것은 부감독님의 인원이다. 

 

부감독이 필요한 경우는 총감독이 감독하지 못한 사람이 있는 경우

- Ai - B > 0 

 

필요한 부감독님 인원은

• (Ai - B)%C == 0 일 때, 
  • (Ai-B)/C
• (Ai-B)%C != 0 일 때, 
  • (Ai-B)/C + 1

 

풀이가 필요할까..?

 

---

 

 

 

조건의 수가 크기 때문에 결과를 담는 변수 타입을 큰 걸로 잡아야 한다.

• 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
• 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.
• 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

answer만 long long으로 선언해줘도 된다. 

최악의 경우, (N x Ai)이 100만 X 100만을 저장해야 하기 때문에 int로는 수를 담지 못한다.

 

A, B, C를 long long으로 선언하면 메모리를 엄청 잡아 먹는다. 

 

 

💾  소스

#include <iostream>

int main()
{
    long long answer = 0l;
    int N, B, C;
    int A[1000001];
    
    std::cin >> N;
    for(int i=0; i<N; ++i)
    {
        std::cin >> A[i];
    }
    std::cin >> B >> C;
    
    
    for(int i=0; i<N; ++i)
    {
        if((A[i]-B) > 0)
        {
            answer += ((A[i]-B)%C ==0 ? (A[i]-B)/C : (A[i]-B)/C +1);
        }
    }
    
    std::cout << answer + N; // 총감독은 실험실 당 1명이니까 무조건 N명 필요함
    
    return 0;
}