BOJ 11659번, 11660번: 구간 합 구하기 4, 5

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

아이디어:

prefix sum(누적 합)을 이용하여 풀 수 있는 문제이다. 누적합이라는 문제풀이 도구 방식을 잘 기억해 놓아야 할 것 같다. 4번 문제는 일차 배열이고, 5번 문제는 2차 배열인데 둘 다 누적합을 이용하면 그리 어렵지 않게 풀 수 있었다.

 

11659번 코드:

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

#누적 합. pre_sum[i] = i까지의 누적 합
pre_sum = [0]*(n+1)

##이부분이 누적합 로직에서 중요한 부분.
for i in range(1, n+1):
    pre_sum[i] = pre_sum[i-1] + arr[i-1]

for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    print(pre_sum[j] - pre_sum[i-1]) ##이것도 누적합 로직에서 중요한 부분

11660번 코드:

import sys
n, m = map(int, sys.stdin.readline().split())
#pre[i][j] = (1,1)~(i,j)까지의 합
pre = [[0]*(n+1) for _ in range (n+1)]
arr = []

for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))

#pre 채우기
for i in range(1, n+1):
    for j in range(1, n+1):
        #이거 잘 이해하기, 그림 그리면 쉬움.
        pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + arr[i-1][j-1]

for _ in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    #위의 식과 비슷함.
    print(pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1])