[백준] 11660 구간합 구하기5 (python)

맨 처음 풀이 > 시간 초과

# 16:55~
# 바로
import sys
from collections import deque
sys.stdin=open("input.txt", "r")
input=sys.stdin.readline

def Make_sum_board():
  for i in range(n):
    for j in range(n):
      # j=0일 때 예외처리
      if i==0 and j==0:
        sum_board[i][j]=board[i][j]
      elif j==0:
        sum_board[i][j]=sum_board[i-1][j]+board[i][j]
      else: # 첫번째 라인에서 이거 뭔가 안되는듯.
        if i==0:
           sum_board[i][j]=sum_board[i][j-1]+board[i][j]
        else:
          line_sum=sum_board[i-1][j]-sum_board[i-1][j-1]
          sum_board[i][j]=sum_board[i][j-1]+board[i][j]+line_sum
        
def Cumul_sum(x1, y1, x2, y2):
  #out of index 오류 방지
  ans=0
  a=sum_board[x2][y2]
  
  if x1==0:
    b1=0
  else:
    b1=sum_board[x1-1][y2]

  if y1==0:
    b2=0
  else:
    b2=sum_board[x2][y1-1]

  if b1==0 or b2==0:
    c=0
  else:
    c=sum_board[x1-1][y1-1]

  ans=a-b1-b2+c
  return ans

 
def solution():
  global ans
  # 총합 구하기
  Make_sum_board()

  # 구간합 구하기
  
  for i in range(m):
    arr=arr_range[i]
    # 인덱스화 하기 위해 -1
    ans_list[i]=Cumul_sum(arr[0]-1, arr[1]-1, arr[2]-1, arr[3]-1)

if __name__=="__main__":
  n, m=map(int, input().split())
  board=[]
  sum_board=[[False]*n for _ in range(n)]
  ans_list=[False]*m

  for _ in range(n):
    board.append(list(map(int, input().split())))
  arr_range=[]
  for _ in range(m):
    arr_range.append(list(map(int, input().split())))
  solution()
  for x in ans_list:
    print(x)

시간이 오래 걸린 이유

• Make_sum_board()와 Cumul_sum() 함수 모두 조건 검토, 예외 처리에 너무 많은 시간 낭비를 했다.
  이를 해결하기 위해서는 합을 구한 board의 i, j에 대해서도 0이라는 완충지역을 두어서 예외사항을 최소화 해야 한다.
• 이걸 쉽게 알아보는 방법은 x=0일 경우, y=0일 경우 예외사항이 너무 많이 나오거나, 이 문제처럼 x1, y1, x2, y2 값을 줄 때 처음 번호를 1로 줄 때 알아차리고 0완충지역을 넣어서 간소화 해야 한다.

모범답안

# 모범 답안
# 아이디어는 비슷한 것 같은데 뭐가 차이나는거지?
import sys
sys.stdin=open("input.txt", "r")
input=sys.stdin.readline


N,M = map(int,input().split())
D = [[0 for _ in range(N+1)]]
## 합 좌표 D 만들기
for i in range(1,N+1): # i, j는 합 넣을 곳(D)의 좌표. D[i][j]
	S=0
	d=[0]
	j=0
	for a in list(map(int,input().split())): #바로 읽으면서 이걸 사용해버린다. 어차피 내가 할 프로그래머스는 이렇게 하는 거 아니다.
		S+=a;j+=1
		# d=[0, 1, 3, 6, 10]
		d.append(D[i-1][j]+S)
	D.append(d) 

# 구간합 구하기
for _ in range(M):
	x1,y1,x2,y2=map(int,input().split())
	print(D[x2][y2]-D[x1-1][y2]-D[x2][y1-1]+D[x1-1][y1-1])

구간합 풀이 설명

a에서 b1, b2를 빼주고 겹치는 부분인 c를 다시 더해준다. 그러면 2, 2, 4, 4 인 부분의 구간합을 구할 수 있다.

모범답안 보고 고친 내 풀이

# 모범 답안 보고 수정한 내 답안
# 아이디어는 비슷한 것 같은데 뭐가 차이나는거지?
import sys
sys.stdin=open("input.txt", "r")
input=sys.stdin.readline

# 구간합 구하기
def CumulSum(D):
  for i in range(m):
    x1, y1, x2, y2=scope[i]
    print(D[x2][y2]-D[x1-1][y2]-D[x2][y1-1]+D[x1-1][y1-1])

# D만들기
def solution():
  D=[[0]*(n+1)] # D에 완충 넣어서 Cumul_sum에서 listOutOfRange error 피할 수 있도록.
  for i in range(1, n+1):
    d=[0]
    s=0 # 해당 행 누적합
    for j in range(1, n+1):
      s+=board[i-1][j-1]
      d.append(D[i-1][j]+s) #바로 위에 값이랑, 해당 board값이랑 더해줌.
    D.append(d)
  CumulSum(D)


if __name__=="__main__":
  n, m=map(int, input().split())
  board=[[] for _ in range(n)]
  scope=[[] for _ in range(m)]
  for i in range(n):
    board[i]=list(map(int, input().split()))
  for i in range(m):
    scope[i]=list(map(int, input().split()))
  solution()