[python] 백준 11660번 - 구간 합 구하기 5

11660번: 구간 합 구하기 5 (acmicpc.net)

11660번: 구간 합 구하기 5

 

백준 단계별 알고리즘의 누적합 카테고리에 있는 문제이다.

처음에는 누적합을 쓰는 것이 익숙하지 않았는데

이젠 나름 잘 적용하는 것 같다.

 

표의 크기와 수가 주어지면 구간합을 구하는 문제인데

처음에는 문제를 잘못 이해해서 테스트 케이스는 통과하였으나 오답처리되었다.

 

예를들어 4*4인 표에서 (2,2)부터 (3,4)까지의 구간합을 구한다고 친다면

(2,2), (2,3), (2,4), (3,2), (3,3), (3,4)의 합을 구해야 하는데

(2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4)의 합을 구하는 것으로 생각해서

 

누적합을 저장하는 2차원 배열에 (0,0) 인덱스부터 마지막까지 계속해서 누적합을 저장하는 방식으로 아래와 같이 

문제를 풀었다.

 

import sys
input = sys.stdin.readline
n,m = map(int, input().split())

tmp = [[0]*n for _ in range(n)]	# 누적 합 저장 배열
lst=[]

for i in range(n):
    lst.append(list(map(int, input().split())))

#처음 인덱스부터 끝까지 누적합 저장       
for i in range(n):
    for j in range(n):
        sum += lst[i][j]
        tmp[i][j] = sum
        
for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2 and y1 == y2:	
        print(lst[x1-1][y2-1])
    elif x1 == y1 == 1 and x2==y2==n:
        print(tmp[x2-1][y2-1])
    else:
        print(tmp[x2-1][y2-1] - tmp[x1-1][y1-1])

 

문제를 이해한 후 수정한 코드는 아래와 같다.

 

import sys
input = sys.stdin.readline
n,m = map(int, input().split())

tmp = [[0]*n for _ in range(n)]
lst=[]

for i in range(n):
    lst.append(list(map(int, input().split())))
    

#누적합 2차원 배열에서 각 행마다 누적합을 구하였다.
for i in range(n):
    sum = 0
    for j in range(n):
        sum += lst[i][j]
        tmp[i][j] = sum

for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    
    start = y1-2	
    
    if x1==x2 and y1==y2:
        print(lst[x1-1][y1-1])
    else:
        sum=0
        for i in range(x1-1, x2 ):
            if start<0:		#	y가 음수일 경우는 해당 행의 마지막 누적합을 구하는 것과 같다.
                sum += tmp[i][y2-1]
            else:
                sum += tmp[i][y2-1]-tmp[i][y1-2]
        print(sum)

그리고 해결!