S1 11660. 구간 합 구하기 5

문제 보기 :  11660번: 구간 합 구하기 5

---

문제

• 정답률 : 43%

---

작성 코드

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
ls = list(list(map(int,input().split())) for _ in range(n))

for i in range(n): #행
    for j in range(n): #열
        if i == 0 and j == 0 :
            continue
        elif i == 0:
            ls[i][j] += ls[i][j-1]
        elif j == 0:
            ls[i][j] += ls[i-1][j]
        else:
            ls[i][j] += (ls[i-1][j]+ls[i][j-1]-ls[i-1][j-1])


for i in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    x1 -= 1 ; x2 -= 1; y1 -= 1;y2 -= 1
    if x1 == 0 and y1 == 0 :
        print(ls[x2][y2])
    elif x1 == 0:
        print(ls[x2][y2]-ls[x2][y1-1])
    elif y1 == 0:
        print(ls[x2][y2]-ls[x1-1][y2])
    else:
        print(ls[x2][y2]-ls[x1-1][y2]-ls[x2][y1-1]+ls[x1-1][y1-1])

---

풀이

처음 입력 받은 ls가 아래와 같다면,
[[1, 2, 3, 4],
[2, 3, 4, 5],
[3, 4, 5, 6],
[4, 5, 6, 7]]

[[1, 3, 6, 10], ← 맨 윗줄은 누적 합으로 업데이트
[2, 3, 4, 5],
[3, 4, 5, 6],
[4, 5, 6, 7]]

[[1, 3, 6, 10],
[3, 8, 15, 24], ← 그 다음 줄은 맨 앞/뒤 칸은 위에서만 끌어오기, 가운데 칸은 왼쪽/위에서 끌어와 합하며 업데이트
[3, 4, 5, 6],
[4, 5, 6, 7]]
이런 방식으로 진행된다.

그래서 최종적으로 만들어지는 ls는 아래와 같다.
[[1, 3, 6, 10],
[3, 8, 15, 24],
[6, 15, 27, 42],
[10, 24, 42, 64]]

그럼 이제 나머지 m번씩 4개의 좌표를 받아서 해당 구간의 합을 구해야 되는데, 케이스를 분리하게 된다.

1. 시작좌표가 0,0이면 업데이트 시킨 좌표 그대로 적용시켜서 마지막 x2,y2 좌표에 해당하는 값를 출력하면 된다.

2. 시작좌표 중 x가 0이면 첫번째 행부터 시작한다는 것이고, y는 0보다 큰 열을 가지는 경우다.
그러면 x2,y2 좌표에 해당하는 값에서 같은 행, y1보다 앞 열의 값만 빼면 된다.
그니까 만약 (1,2), (2,4)이라면 24-3=21로 계산하게 되고,
(코드안에서 모든 좌표에 1을 빼서 실제 입력이 1인 경우가 행index가 0인 경우다.)

이렇게 더해서 21로 일치한다.

3. 시작좌표 중 y가 0이면 열은 0부터 시작하는데 x는 0보다 큰 행을 가지는 경우다.
그러면 x2,y2 좌표에 해당하는 값에서 같은 열, x1보다 앞 행의 값만 빼면 된다.
만약 (2,1), (4,3)이라면 42-6=36으로 계산하게 되고,

이렇게 더해서 36으로 일치한다.

4. 마지막 케이스는 중간에 다 떠있을 때, 다시 말해 시작점이 앞에 걸쳐있지 않을 때다.
그러면 2번, 3번을 모두 실행한 다음에, 첫시작 좌표의 대각선(?) 값을 더하면 답이다.
만약 (2,2), (4,3)이라면 42-10-6+1=27로 계산하게 되는데, 그림으로 나타내면

이렇게 더해서 27이 된다. 좀 많이 복잡하고 규칙을 찾아야해서 다음에 한번 더 풀이해야겠다.