[Baekjoon]백준 11660 구간 합 구하기 5(실버 1) - Python

문제설명

예제

문제를 살펴보면 인덱스 두 개를 입력받고, 그 인덱스 구간의 합을 구하는 문제이다

이때까지의 문제와 다른 점은 2차원 배열이라는 점, 그리고 x좌표의 범위에 따라 합이 제한된다는 것이다

두 번째 말에 대해 다시 말하자면, 예를 들어

1 2 3 

4 3 2 

3 4 1

라는 표가 주어져있을때 (2,2)부터 (3, 3)까지의 합을 구하는 것에 (3, 1)은 포함되지 않는다는 점이다

 

그래서 처음에 이 문제를 풀기 위한 로직으로 각 행마다 누적합을 계산해두고, index를 입력받으면

for문을 통해 부분합을 구하여 변수 하나에 해당 값을 계속해서 저장하여 출력하도록 하였다

위의 예를 통하여 설명하자면 누적합이 [1, 3, 6], [4, 7, 9], [3, 7, 8]로 저장되어있을텐데, 

 (2, 2), (3, 3)이 입력되었을 때 9-4 = 5, 8-3 = 5 가 되어 둘의 합을 더한 10이 출력되게 작성하였다

size, cnt = map(int, input().split())
board = []

for _ in range(size):
    board.append(list(map(int, input().split())))
    
prefix_board = [[0] * (size + 1) for _ in range(size + 1)]
for i in range(size):
    for j in range(size):
        prefix_board[i][j + 1] = prefix_board[i][j] + board[i][j]
    
for _ in range(cnt):
    x1, y1, x2, y2 = map(int, input().split())
    result = 0
    for i in range(x1, x2 + 1):
        # print(prefix_board[i-1][y2])
        result += prefix_board[i-1][y2] - prefix_board[i-1][y1 - 1]
    print(result)

그러나 해당 코드를 제출하였더니 시간초과가 발생하였다

그래서 이번에는 2차원 배열 전체의 누적합에 대해 계산하는 방법으로 생각해보았다

x좌표에 따라 포함되지 않는 부분이 있어서 그냥 계산을 하면 안되기 때문에 그에 유의하여 작성하였다

누적합을 구할 때, 해당 행 - 1한 위치의 누적합, 해당 열 - 1한 위치의 누적합을 더해주어야하고, 이렇게되면

해당 index의 행 - 1, 열 - 1한 위치의 누적합이 중복으로 더해지기 때문에 이를 빼주어야한다

result[i][j] = result[i][j-1] + result[i-1][j] - result[i-1][j-1] + board[i-1][j-1]

이 부분이 위에서 설명한 코드에 대한 설명이다

그리고 구간합을 구하는 과정도 유의해야하는데 위의 예시처럼

1 2 3 

4 3 2 

3 4 1

인 상황일 때 (2, 2), (3, 3)이 주어지게 된다면 단지 값만 빼면 되는것이 아니다

3,3의 위치의 누적합에서 1열의 누적합들도 빼주어야하고, 1행의 누적합들도 빼주어야한다

이후에 1,1의 위치의 값은 두 번 뺐기때문에 이 위치의 누적합을 다시 더해주어야 원하는 범위의 구간합을 구할 수 있다

answer = result[x2][y2] - result[x2][y1-1] - result[x1-1][y2] + result[x1-1][y1-1]

그래서 최종적으로 제출한 코드는 밑의 코드와 같다

size, cnt = map(int, input().split())
board = []

for _ in range(size):
    board.append(list(map(int, input().split())))
    
result = [[0] * (size + 1) for _ in range(size + 1)]
for i in range(size + 1): # 누적 합 저장
    for j in range(size + 1):
        result[i][j] = result[i][j-1] + result[i-1][j] - result[i-1][j-1] + board[i-1][j-1]
        
for i in range(cnt): # 구간 합 구하기
    x1, y1, x2, y2 = map(int, input().split())
    answer = result[x2][y2] - result[x2][y1-1] - result[x1-1][y2] + result[x1-1][y1-1] # 겹치는 부분 더하기
    print(answer)

끝인줄 알았지만...시간초과가 발생한다

아무래도 입력받은 수가 많은 탓인거같아서 sys모듈을 사용하여 코드를 재작성하였고, 정답임을 확인할 수 있었다

import sys

size, cnt = map(int, input().split())
board = []

for _ in range(size):
    board.append(list(map(int, sys.stdin.readline().split())))
    
result = [[0] * (size + 1) for _ in range(size + 1)]
for i in range(size + 1): # 누적 합 저장
    for j in range(size + 1):
        result[i][j] = result[i][j-1] + result[i-1][j] - result[i-1][j-1] + board[i-1][j-1]
        
for i in range(cnt): # 구간 합 구하기
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    answer = result[x2][y2] - result[x2][y1-1] - result[x1-1][y2] + result[x1-1][y1-1] # 겹치는 부분 더하기
    print(answer)