[백준]_11659번 : 구간 합 구하기 4(파이썬 and C언어)

11659번: 구간 합 구하기 4

해석

사용자가 입력한 배열에서 i 번째 요소부터 j 번째 요소까지의 합을 출력하면 된다. 단 i 와 j 가 같을 때는 해당 요소만 출력한다. 문제에서 무리한 요구를 하고 있지는 않지만 시간 초과, 런타임 에러, 메모리 초과만악의 근원들..들을 조심해야 함을 알 수 있다. 쉬운 문제가 괜히 실버 3이 아닐 것이다..

---

전략

구간 합이기 때문에 원하는 구간만 잘라서 합을 구해보는 방법이 있을 것이다. 이 방법이 가장 간단해 보이니 시도해 보자.

시도 1(Python)

import sys

input = sys.stdin.readline

size, cnt = map(int, input().split())
ls = list(map(int, input().split()[:size]))

for _ in range(cnt):
    sum = 0
    el=list(map(int, input().split()))
    for i in range(el[0] - 1, el[1]):
        sum += ls[i]
    print(sum)

<평가> 시간 초과가 나온다... 아마도 시간 복잡도가 O(N*N) = O(n^2)이라 그런 것이라 예상 된다. 시간 복잡도를 낮추는 방법이 무엇이 있을까?

그것은 바로 애초에 0 ~ ( i - 1 ) 번째 인덱스까지 무지성으로 더한 값들을 새로운 배열에 저장해 놓고 필요한 부분들만 꺼내서 빼주면 된다. 예를 들어 배열이 [ 1, 2, 3, 4, 5 ]인 상태에서 사용자가 3( i ) 5( j )를 입력하면 새로운 배열에 3 직전 까지 합한 값(sum1), 5까지 합한 값(sum2)을 저장해 주고 sum2-sum1을 계산해 주면 된다. 생각보다 멍청한 방법이긴 하지만 시간 복잡도는 확실히 줄일 수 있다. 

수정

import sys

input = sys.stdin.readline

size, cnt = map(int, input().split())
ls = list(map(int, input().split()[:size]))

reposit = [0]
sum = 0
for i in ls:
    sum += i
    reposit.append(sum)

for _ in range(cnt):
    f, s = map(int, input().split())
    print(reposit[s] - reposit[f - 1])

reposit에 0을 먼저 대입한 이유는 사용자가 1 1 을 입력했을 때 마지막 출력 줄에 의하면(print(reposit[s] - reposit[f - 1])) s와 f가 같더라도 1만큼의 인덱스 차이가 있어야 한다. 따라서 0 인덱스에 0을, 1 인덱스부터 대입값들을 저장하는 방식으로 풀었다. 

---

시도 2(C언어)

#include <stdio.h>

int main() {
    int arr[100001]={0};
    long long repo[100001]={0};
    int n,m;
    scanf("%d %d",&n,&m);
    for(int a=0; a<n; a++){
        scanf("%d", &arr[a]);
    }
    int sum=0;
    repo[0]=0;
    for(int j=0;j<n;j++)
    {
        sum+=arr[j];
        repo[j+1]+=sum;
    }		
    for(int i=0;i<m;i++)
    {
        int f,s;
        scanf("%d %d",&f,&s);
        printf("%d\n",repo[s]-repo[f-1]);
    }
    return 0;
}

합을 구하는 배열 repo는 저장값이 많이 커질 수 있기 때문에 넉넉히 long long으로 선언해 준다.