[백준11660&파이썬] 누적합을 구하는 기본문제

# 문제

백준 11660 구간 합 구하기 5 파이썬 풀이

11660번: 구간 합 구하기 5

# 코드

import sys

def print2D(arr) :
  for i in arr :
    print(*i)
  print()

N,M = map(int,sys.stdin.readline().split())

board = list()
for _ in range(N) :
  line = list(map(int,sys.stdin.readline().split()))
  board.append(line)

targets = list()
for _ in range(M) :
  target = list(map(int,sys.stdin.readline().split()))
  targets.append(target)

# board를 누적합 배열로 만들어 놓고, 문제 풀이시 한번에 solve가능하도록 하자
for row in range(N) :
  for col in range(1,N) :
    board[row][col] += board[row][col-1]

# print2D(board)


for target in targets :
  r1,c1,r2,c2 = target
  r1 -= 1; c1 -=1; r2 -=1; c2 -=1; # 인덱싱 보정
  result = 0

  for r in range(r1,r2+1) :
    result += board[r][c2]
    if c1 == 0 :
      minus = 0
    else :
      result -= board[r][c1-1]

  print(result)

# 풀이

• 기존 O(N^2)의 완전탐색으로 문제를 풀었을때 시간초과가 발생했다. O(N^2)으로 풀려야할 것 같았지만 테스트케이스 M번에 대해서 구해야하고, M이 최대 100,000이기 때문에 O(N^2 * M )의 시간복잡도를 가지기에 시간초과가 나는 것이 당연하다.
• 각 행(row)별로 누적합을 구해 borad를 갱신한 뒤, 아래와 같은 방법으로 O(N)으로 구할 수 있는 방법을 사용했다.

 

• 참고 방식으로 풀이하면 O(1)이면 풀이가 가능하다. ( 누적합을 구하는 연산 제외 )

# 참고

[python/파이썬] 백준 11660 구간 합 구하기 5