13458 시험 감독

 

#include <iostream>
#include <algorithm>
using namespace std;

int a[1000000];

int main() {
    int n, b, c;
    int sum = 0;
    
    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++)
        sum += (max(a[i]-b, 0)+c-1)/c + 1;
    printf("%d", sum);
}

열심히 알고리즘을 짰고

기분좋게 돌렸는데 틀렸다!

심지어 입력예시 다 돌려봤는데 에러도 안 떴는데!

 

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;

int a[1000000];

int main() {
    int n, b, c;
    i64 sum = 0;
    
    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++)
        sum += ((max(a[i]-b, 0)+c-1)/c + 1);
    printf("%lld", sum);
}

계속 머리 싸매다가 알고보니 계산에서 오버플로우 때문에 터졌다.

입력 받을 때 최대 값이 10^6 이라 int로 해도 될 줄 알았는데, 감독관의 합을 구할 때 문제가 생겼다. 

만약 시험장이 10^6개고 응시자가 10^6명인데, 감독관은 한명씩 밖에 없다면 10^6 x 10^6 = 10^12이 되어 백퍼 터진다.

 

이렇게도 터질 수 있구나..

틀렸을때 이 원인도 고려해야겠다....