[python] 백준 - 11660. 구간 합 구하기 5

🤔문제 해결

1. S1 | DP
2. (0,0) 부터 리스트의 모든 지점까지 각각의 합을 구한다.
3. 2번을 수행하고 나면 아래와 같은 결과를 얻을 수 있다.
   
4. 합을 누적한 리스트로 아래 그림처럼 구하고자 하는 영역을 구하고 필요없는 부분은 빼주면 된다.
5.  여기서 많이 헷갈릴 수 있는데 문제는 1,1부터 시작하지만 우리는 0,0부터 시작한다.
   또, 빼줘야하는 영역(빨간색) 부분은 두번 빼는 경우가 있기 때문에 다시 더해줄 영역(초록색)을 한번 더해준다.
6. 여기서 끝이 아니다. x축이 처음부터 인경우와 y축이 처음부터인 경우, 둘 다 아닌경우 이 3가지 경우로 나눠서 풀어줘야한다.

 

 

 

💨 시간초과 때문에 힘들었던 문제...

 

💻소스 코드

import sys
from itertools import accumulate  # 누적 합을 구해주는 내장함수

if __name__ == "__main__":
    N, M = map(int, input().split())
    numbers = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

    # 0,0 부터 n1,n2까지 각각의 합을 미리 구해놓기
    for i in range(N):
        numbers[i] = list(accumulate(numbers[i]))
    for i in range(1, N):
        for j in range(N):
            numbers[i][j] += numbers[i-1][j]
    print()
    for row in numbers:
        print(row)

    orders = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
    for x1, y1, x2, y2 in orders:
        all = numbers[x2-1][y2-1]  # 전체

        if x1 == 1 and y1 == 1:
            print(all)
            continue

        minus2 = numbers[x2 - 1][y1 - 2]  # 뺄부분 1
        minus1 = numbers[x1 - 2][y2 - 1]  # 뺄부분 2
        if x1 == 1:
            print(all-minus2)
        elif y1 == 1:
            print(all-minus1)
        else:
            plus = numbers[x1 - 2][y1 - 2]  # 중복으로 빼서 다시 더해야될 부분
            print(all-minus1-minus2+plus)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

11660번: 구간 합 구하기 5

---

---

---

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.