[백준] 구간 합 / 구간 합 구하기 5

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

👀👉 구간 합 기본 개념 및 전략

 

Input

표의 크기 N(NxN), 합을 구해야 하는 횟수 M(아주 큼)

둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다

다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어짐

ex. 
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

N = 4, M = 3

 

Input = 

[[1 2 3 4],

[2 3 4 5],

[3 4 5 6],

[4 5 6 7]]

 

Output = 

[[2 2 3 4],

[3 4 3 4],

[1 1 4 4]]

 

output

(x1, y1)부터 (x2, y2)까지 합, 총 M개 (각 줄에 하나의 값, M줄)

 

ex. 

27

6

64

 

 

문제 풀이

1. 단순한 구간 합으로 ,,,, 단순 비효율적으로 => 시간 초과

#시간초과

import sys

[N, M] = list(map(int, sys.stdin.readline().split()))
inputs = []
outputs = []
for i in range(N+M):
    if i < N:
        inputs.append(list(map(int, sys.stdin.readline().split())))
    else:
        outputs.append(list(map(int, sys.stdin.readline().split())))

sum_lst = [[0 for _ in range(N)] for _ in range(N)]  # [[0]*N]*N
max_y = max([x[3] for x in outputs])
sums = 0

for y in range(max_y):
    for x in range(N):
        sums += inputs[y][x]
        sum_lst[y][x] = sums

for [a, b, c, d] in outputs:
    if a==c and b==d:
        print(inputs[c-1][d-1])
        continue
    elif a==1 and b==1:
        print(sum_lst[c-1][d-1])
        continue
    elif a>=2 and b==1:
        print(sum_lst[c-1][d-1] - sum_lst[a-2][-1])
        continue
    else:
        f_sum = 0
        for t in range(a-1, c):
            f_sum += sum_lst[t][d-1] - sum_lst[t][b-2]
        print(f_sum)

2. 합 배열과 구간 합의 변용 (중복처리 중요)

문제에 따른 조작적 정의

- 합 배열 :

• 단순히 1번 원소부터 특정 원소까지 다 더한 합이 아니라, 처음부터 직사각형 형태의 합으로 구함
• 점화식의 초항처럼, x=0, y=0일 때의 가장자리 원소를 별도로 구해줌 (base)
• 가장자리 원소(x,y)까지 직사각형 형태의 합 = (x-1까지 직사각형) + (y-1까지 직사각형) - ((x-1, y-1)까지 직사각형)

- 구간 합: 직사각형 형태로 도출될 수 있도록 구함

• (x2,y2)에서 합 배열의 원소 - (x1-1, y2)에서 합 배열의 원소 - (x2, y1-1)에서 합 배열의 원소 + (x1-1, y1-1)에서 합 배열의 원소

import sys

[N, M] = list(map(int, sys.stdin.readline().split()))
inputs = []
outputs = []
for i in range(N+M):
    if i < N:
        inputs.append(list(map(int, sys.stdin.readline().split())))
    else:
        outputs.append(list(map(int, sys.stdin.readline().split())))

sum_lst = [[0 for _ in range(N)] for _ in range(N)]  # [[0]*N]*N
max_y = max([x[3] for x in outputs])

#default setting
sum_lst[0][0] = inputs[0][0]
for x in range(1,N):
    sum_lst[0][x] = sum_lst[0][x-1] + inputs[0][x]
    
for y in range(1,max_y):
    sum_lst[y][0] = sum_lst[y-1][0] + inputs[y][0]


for y in range(1, max_y):
    for x in range(1, N):
        sum_lst[y][x] = sum_lst[y-1][x] + sum_lst[y][x-1] - sum_lst[y-1][x-1] + inputs[y][x]

    
for [x1, y1, x2, y2] in outputs:
    if x1 == x2 and y1==y2:
        print(inputs[x1-1][y1-1])
    elif x1>=2 and y1 >=2:
        print(sum_lst[x2-1][y2-1] - sum_lst[x1-2][y2-1] - sum_lst[x2-1][y1-2] + sum_lst[x1-2][y1-2])
    elif x1==1 and y1>=2:
        print(sum_lst[x2-1][y2-1] - sum_lst[x2-1][y1-2])
    elif x1>=2 and y1==1:
        print(sum_lst[x2-1][y2-1] - sum_lst[x1-2][y2-1])
    else:
        print(sum_lst[x2-1][y2-1])