백준 11660번 <구간 합 구하기 5>

백준 알고리즘 11660번

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

11660번: 구간 합 구하기 5

---

11660번

입력으로 첫 줄에 표의 크기 N과 구간 합을 구해야하는 횟수 M이 주어진다.

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

그 후 M개의 줄에는 x1, y1, x2, y2 4개의 정수가 주어진다.

 

출력으로는 입력에서 M개의 줄에 걸쳐 들어온 (x1, y1)부터 (x2, y2)의 합을 구해 출력한다.

---

문제 해결

https://seunghee114-blog.tistory.com/202

구간 합 구하기

위의 글에 설명된 방법을 이용하여 문제를 풀었다.

---

이때 예외 상황으로

1. (x1, y1) = (0, 0)인 경우

2. x1이 0이거나 y1이 0인 경우

두 가지 경우가 있다.

1번의 경우에는 그냥 sum[x2][y2]를 출력하면 되고

2번의 경우에는 또 두 가지 경우로 나뉜다. 

x1이 0인 경우에는 pink와 blue를 구할 수 없으므로 green만 구하여 공식에 적용하면 되고

y1이 0인 경우에는 pink와 green을 구할 수 없으므로 blue만 구하여 공식에 적용하면 된다.

---

코드

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

result = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    temp = list(map(int, input().split()))
    value = 0
    for j in range(n):
        if i == 0:
            value += temp[j]
            result[i][j] = value
        else:
            if j == 0:
                result[i][j] = temp[j] + result[i-1][j]
            else:
                result[i][j] = temp[j] + result[i-1][j] + result[i][j-1] - result[i-1][j-1]
idx = []

for _ in range(m):
    temp = list(map(int, input().split()))
    idx.append(temp)

for i in range(m):
    x1, y1, x2, y2  = idx[i]
    x1 = x1 - 1
    y1 = y1 - 1
    x2 = x2 - 1
    y2 = y2 - 1

    if x1 == 0 or y1 == 0:
        if x1 ==0 and y1 ==0:
            print(result[x2][y2])
        else:
            if y1 == 0:
                blueX = x1 - 1
                blueY = y2
                print(result[x2][y2] - result[blueX][blueY])
            else:
                greenX = x2
                greenY = y1 - 1
                print(result[x2][y2] - result[greenX][greenY])
    else:
        pinkX = x1 - 1
        pinkY = y1 - 1
        greenX = x2
        greenY = y1 - 1
        blueX = x1 - 1
        blueY = y2
        print(result[x2][y2] + result[pinkX][pinkY] - result[greenX][greenY] - result[blueX][blueY])

---

결과

---