Baekjoon 13458

1) 문제 분석

  방심하고 있다가 뒤통수 맞은 듯한 문제. 문제 자체는 굉장히 쉬운데 주어진 입력의 범위를 잘 살펴봐야 한다. int 자료형으로 1,000,000 정도는 물론 커버할 수 있지만, 만약 C와 B가 각각 1이고 N과 N개의 Ai의 값이 1,000,000 이라면? 10^12이라는 큰 수가 정답이 되는데, int의 크기가 32비트라면 int 자료형의 최댓값은 2,147,483,648 이기 때문에 정답이 틀리게 나온다. 따라서 변수 타입을 적절하게 설정해주어야 한다.
  그렇다고 모든 변수들을 다 크게 잡으면 메모리를 불필요하게 많이 차지하기 때문에 필요한 만큼만 해줘야 한다. 가령, 아래 코드에서 모든 변수를 long long으로 잡으면 9676 kb나 차지하는데, 아래처럼 total 변수만 long long 으로 잡으면 거의 절반 가까이 절약된다. 아무래도 cases 배열의 길이가 길어서 그런 듯 하다.
  정답률이 왜 이렇게까지 낮은지는 모르겠지만 이 점만 염두해두면 매우 쉽게 풀리는 문제이다. 그리고 문제가 약간 애매해서 착각했는데, 모든 시험장마다 총 감독관은 꼭 한 명씩 있어야 하는 것 같다. 알고리즘이라고 할 것도 없다. 그냥 총감독관이 감독할 수 있는 응시자 수를 빼고, 그 값이 0보다 크면 필요한 감독관 수의 최솟값이 1이고, 그렇지 않다면 부감독관 몇 명이 더 필요한지만 계산해주면 된다.

2) 코드

#include <iostream>

using namespace std;

int main(){
    int N;
    int cases[1000000];
    int B, C;
    int min;
    long long total;

    cin >> N;
    for(int i=0; i<N; i++)
        cin >> cases[i];

    cin>>B; cin>>C;
    total = 0;

    for(int i=0; i<N; i++){
        if(cases[i]-B>0) {
            min = (cases[i] - B) / C +1;
            if ((cases[i] - B) % C) min++;
        }
        else min = 1;

        total += min;
    }

    cout << INT_MAX;
}

3) 개선점

채점 현황을 보니, 내 코드는 500ms 정도의 시간이 걸리는 것으로 나오는데, 같은 c++ 코드인데 시간이 100~200ms 사이인 경우들이 보였다. 그래서 어떻게 하면 시간을 줄일 수 있는지 고민해보았다. 우선 어디에서 시간이 많이 소요되는지 알아야 하는데, 아무래도 입출력 쪽이 의심돼서 다음과 같이 추가했더니 120ms 정도로 시간이 줄어들었다!

ios_base::sync_with_stdio(false);

sync_with_stdio(false) 함수는 표준 c++ 스트림과 표준 c 스트림을 동기화 시키는데 사용된다. 파라미터로 true를 전달하면 동기화되고 false이면 동기화되지 않는다. Cpp 사이트에 들어가서 method 설명을 더 자세히 살펴보면 다음과 같이 말하고 있다.

“In practice, this means that the synchronized C++ streams are unbuffered, and each I/O >operation on a C++ stream is immediately applied to the corresponding C stream’s buffer. >This makes it possible to freely mix C++ and C I/O.
In addition, synchronized C++ streams are guaranteed to be thread-safe (individual >characters output from multiple threads may interleave, but no data races occur)
If the synchronization is turned off, the C++ standard streams are allowed to buffer their >I/O independently, which may be considerably faster in some cases.
By default, all eight standard C++ streams are synchronized with their respective C >streams.”

즉, I/O 함수를 수행할 때 c++ 스트림이 따로 버퍼를 가지는 대신,c 스트림과 버퍼를 공유한다는 것이다. 만약 동기화하지 않는다면, 각각의 스트림은 버퍼를 따로 가지게 되고 I/O 연산을 따로 처리한다. 따라서 c++ 입출력 함수와 c 입출력 함수를 함께 사용했을 때 어떤 I/O 연산이 먼저 처리 될지 알 수 없으므로 sync_with_stdio(false)를 사용할 때는 이를 주의해야한다.