(python) 백준 11660호 – 섹션의 합 구하기 5

11660: 섹션의 합 찾기 5(acmicpc.net)

백준 단계별 알고리즘의 누적합 범주에 있는 문제입니다.

처음에는 누적 합계를 사용하는 데 익숙하지 않았습니다.

지금은 잘 작동하는 것 같습니다.

테이블의 크기와 개수가 주어졌을 때 간격의 합을 구하는 것은 문제입니다.

처음에는 문제를 잘못 이해해서 테스트 케이스는 통과했지만 오답을 받았습니다.

예를 들어, 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)

해결!