[백준/BOJ/C언어] 14648번 :: 쿼리 맛보기

문제 링크 :: https://www.acmicpc.net/problem/14648

---

 Solution

 

  Prefix sum 알고리즘으로 쉽게 해결할 수 있는 문제입니다. 관련 설명은 아래 링크에서 보실 수 있습니다. 그런데 한 가지 주의해야 할 점이 있습니다. [a, b] 구간의 합을 구하기 위해서 b까지의 부분 합과 a-1까지의 부분합을 알아야 하는데, 편의상 배열의 크기를 (n이 최대 1000이므로) 1001로 선언해 두고 첫 번째 요소의 인덱스가 1이 되도록 코드를 작성하는 경우에는 그대로 b와 a-1까지의 부분 합을 사용해서 구간 합을 구하면 되지만, 첫 번째 요소의 인덱스가 0인 경우에는 b-1과 a-2까지의 부분 합을 구해야 합니다. 이런 사소한 부분에서 실수가 나면 은근 알아차리기 어렵더라구요. 물론 제 경험이 부족한 탓일 가능성이 99.8%이긴 합니다. 또, 숫자를 스왑해 준 뒤에 부분 합 배열을 변경하는 것 잊지 마세요. 아니면 (당연히...) 틀렸습니다를 보게 됩니다. + 수열의 숫자들은 모두 int 형 범위 내지만 이들을 많이 더하면 몹시 커질 수 있으므로 부분 합 배열과 정답 변수는 long long으로 선언해 줘야 합니다. 

---

 Code

 

#include <stdio.h>
int num[1000];
long long sum[1000];
 
void swap(int a, int b) {
    int temp;
    temp = num[a - 1];
    num[a - 1] = num[b - 1];
    num[b - 1] = temp;
}
 
int main() {
    long long ans;
    int i, n, q, kind, a, b, c, d;
    scanf("%d %d", &n, &q);
 
    for (i = 0; i < n; i++) {
        scanf("%d", &num[i]);
        if (i == 0) {
            sum[i] = num[i];
        }
        else {
            sum[i] = sum[i - 1] + num[i];
        }
    }
    
    while (q--) {
        scanf("%d", &kind);
        if (kind == 1) {
            scanf("%d %d", &a, &b);
            if (a == 1) {
                ans = sum[b - 1];
            }
            else {
                ans = sum[b - 1] - sum[a - 2];
            }
            printf("%lld\n", ans);
            swap(a, b);
            for (i = 0; i < n; i++) {
                if (i == 0) {
                    sum[i] = num[i];
                }
                else {
                    sum[i] = sum[i - 1] + num[i];
                }
            }
        }
        else if(kind == 2) {
            scanf("%d %d %d %d", &a, &b, &c, &d);
            if (a == 1) {
                if (c == 1)
                    ans = sum[b - 1] - sum[d - 1];
                else
                    ans = sum[b - 1] - (sum[d - 1] - sum[c - 2]);
            }
            else {
                if (c == 1)
                    ans = sum[b - 1] - sum[a - 2] - sum[d - 1];
                else
                    ans = sum[b - 1] - sum[a - 2] - (sum[d - 1] - sum[c - 2]);
            }
            printf("%lld\n", ans);
        }
    }
 
 
 
    return 0;
}

 

---

 Related

2019/07/27 - [코학/알고리즘] - [알고리즘] Prefix sum(구간 합)에 대해 알아보기