[C++ 백준 풀이] cin, cout과 scanf, printf 차이점 (11659번 : 구간 합 구하기 4)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 11659번 : 구간 합 구하기 4에 대한 풀이 코드와 해설, 그리고 cin, cout과 scanf, printf의 속도 측면에서의 차이점을 다루고 있습니다.

 

 

11659번 : 구간 합 구하기 4

 

N개의 숫자가 입력되고, M개의 테스트케이스 동안 i~j번째 숫자들의 합을 구해 출력하는 문제입니다.

당연히 브론즈 문제가 아니므로, 그냥 더해서 풀면 시간 초과가 나오게 설계되어 있습니다.

따라서 시간을 아끼면서 더욱 빨리 구간 합을 구하는 방법을 이용해야 합니다.

 

 

↓ 복사가 가능한 소스 코드 원문은 아래 접은 글에 정리되어 있습니다.

#include <iostream>
using namespace std;

int main() {
    int N, M, input, sum[100005] = {0, }, a, b;
    scanf("%d %d", &N, &M);
    for(int i=1; i<=N; i++) {
        scanf("%d", &input);
        sum[i] = sum[i-1] + input;
    }
    for(int i=1; i<=M; i++) {
        scanf("%d %d", &a, &b);;
        printf("%d\n", sum[b]-sum[a-1]);
    }
}

 

따라서 이 문제를 가장 빠르게 풀 수 있는 방법은, 1번째 수부터 i번째 수까지의 합을 수를 입력받는 족족 계산해서 배열에 저장해두는 것입니다.

그리고 i번째 수부터 j번째 수까지의 합은, j번째 수까지의 sum에서 i-1번째 수까지의 sum을 빼서 한 번에 구할 수 있습니다.

이를 이용해서 풀이를 하면 O(N) 시간 안에 문제를 해결할 수 있게 됩니다.

 

그러나 중요한 점은 이것보다도, 입출력의 형태에 있습니다.

 

 

위의 코드는 시간 초과가 발생한 코드입니다.

알고리즘 자체에는 문제가 없지만, 원인은 입출력 형태 때문입니다.

cin과 cout은 수행 시간 자체가 scanf나 printf보다 오래 소요됩니다.

따라서 알고리즘이 구조상 문제가 없어 보이는데 시간 초과가 발생한다면 입출력부를 바꾸는 것을 권장합니다.

헤더파일 iostream은 네 개의 입출력 함수를 모두 포함하기 때문에 어떤 것을 사용해도 문제 없습니다.

다만 scanf, printf만 사용할 것이라면 cstido를 선언해도 됩니다.

 

 

입출력부를 수정해보면 위와 같이 80ms라는 제한 시간 안에 해결이 됨을 확인할 수 있습니다.