백준 11659번 문제(구간 합 구하기 4) 파이썬(Python) 풀이 [로밍맨]

문제 링크

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

정답 코드는 아래와 같습니다.

import sys
 
def solve():
  n, m = map(int, sys.stdin.readline().rstrip().split())
  arr = list(map(int, sys.stdin.readline().rstrip().split()))
  s = [0]
  for i in range(n):
    s.append(arr[i] + s[i])
  for _ in range(m):
    i, j = map(int, sys.stdin.readline().rstrip().split())
    print(s[j] - s[i-1])
 
solve()

 

데이터가 나열되어 있을 때 일정 구간의 합을 구하는 것은 프로그래밍 언어를 배운 이후에 해당 언어의 문법을 제대로 익혔는지 확인하는 차원에서 만들어 볼만한 쉬운 문제입니다.

하지만 이 문제는 합을 구하는 행위가 여러번 반복되기 때문에 그리 단순한 문제가 아니게 됩니다.

영상에서 이미 보여드렸다시피, 단순하게 각 요청에 대하여 합을 구하는 방식으로 구현하게 되면 시간 초과가 발생하게 됩니다.

각 요청에 대하여 최대 N번의 연산을 해야하는데, 요청이 최대 M번 이므로 복잡도는 O(MN) 이며, N과 M이 각각 최대 10만 이므로, 곱하면 100억 정도가 되기 때문에 시간 초과가 발생하는 것입니다.

(보통 복잡도에 값을 대입하여 그 값이 1억 정도인 경우 시간 초과가 발생하지 않고 문제가 풀립니다)

 

문제가 잘 풀리지 않는 경우에는 실제로 이런 일이 내가 해야 하는 업무라고 가정을 하고, 데이터를 쭉 나열한 다음에 단순한 방식으로 업무를 몇 번만 처리해보다보면, 도저히 이렇게 해서는 안되겠다는 생각이 절로 들게 될 것입니다.

문제에서는 데이터가 총 10만개, 요청이 총 10만번 인데요.

이게 각각 1000개, 1000번 이라고 가정하고 실제로 해보면 계속해서 같은 구간에 대하여 합을 다시 구해야 하는 비효율이 있음을 깨닫게 될 것입니다.(사실 100개 그리고 100번 이라고 해도 충분할 것입니다)

가령 어떤 요청이 20부터 50까지의 합을 구하라고 해서 구했는데, 다음 요청이 20부터 60까지라고 하면, 사람이라면 떠오를 수밖에 없을 것입니다. 이전 결과에다가 50부터 60까지의 합만 더해야겠다는 생각이 말이죠.

 

728x90

 

결국 비효율적인 중복을 제거하는 것(미리 합을 구해 놓는 것)이 이 문제를 해결하는 방법이라는 것까지는 어렵지 않게 떠올릴 수 있을 것입니다.

핵심은 어떻게 제거할 것인가(어디부터 어디까지의 합을 어떻게 미리 저장할 것인가) 인데요.

다양한 방법이 있습니다만, 여기서는 처음부터 x번째 까지의 합을 미리 구해놓고 그 값들 간의 차이가 일정 구간의 합인 성질을 이용하여 문제를 풀었습니다.

예를 들어서 s[2] 은 1번째, 2번째 원소의 합을 의미하고, s[5] 이면, 1번째, 2번째, 3번째, 4번째, 5번째 원소의 합인 것입니다. 3번째 부터 5번째까지의 합을 구해야 한다면,(양 끝을 포함해야 하므로) s[5] 에서 s[2]을 빼는 것입니다.

s[2] = arr[1] + arr[2]

s[5] = arr[1] + arr[2] + arr[3] + arr[4] + arr[5]

s[5] - s[2] = arr[3] + arr[4] + arr[5]

위와 같은 등식이 성립함을 이용하는 것이죠.

s 를 만드는데 필요한 연산은 아이템의 갯수(N) 만큼 필요할 것이고, 각 요청 M번에 대해서는 뺄셈만 해주면 되기 때문에 결국 복잡도는 O(M+N)이 됩니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=zN8ukzSuUuk 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)