백준 11660번 구간 합 구하기 5 문제풀이, 파이썬

백준 11660번 : 구간 합 구하기 5 문제풀이 [파이썬] 

---

<문제>

 

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)까지 합을 구해 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

27
6
64

예제 입력 2 복사

2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2

예제 출력 2 복사

1
2
3
4

---

 

 

<작성한 코드>

 

#구간 합 구하기 5
import sys

N, M = map(int, sys.stdin.readline().split())
arr = []
prefix_sum = [[0]*(N+1) for _ in range(N+1)]

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

for i in range(1, N+1):
  for j in range(1, N+1):
    prefix_sum[i][j] = arr[i-1][j-1] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]

for _ in range(M):
  x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
  ans = prefix_sum[x2][y2] - prefix_sum[x1-1][y2] - prefix_sum[x2][y1-1] + prefix_sum[x1-1][y1-1]
  print(ans)

---

 

 

<코드 풀이>

 

이전 구간 합에 대한 문제는 아래 포스팅에서 참고

2023.04.13 - [백준 알고리즘] - 백준 11659번 구간 합 구하기4 문제풀이, 파이썬

백준 11659번 구간 합 구하기4 문제풀이, 파이썬

 

 

 

 

본 문제는 이전 문제와는 다르게 1차원 배열이 아닌 

2차원 배열에서의 구간 합을 구해야하는 문제였다. 

이해가 어려운건 아니었지만 그걸 코드로 옮겨서 작성하는데 헷갈려서 종이에 써가면서 알고리즘을

뽑아내고 이해하려고 노력했다. 

 

 

 

import sys

N, M = map(int, sys.stdin.readline().split())
arr = []
prefix_sum = [[0]*(N+1) for _ in range(N+1)]

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

우선 여느 문제들과 마찬가지로 본 문제에서 요구하는 입력값들을 받기 위한 세팅을 해주었다. 

arr 라는 이름에는 문제에서 주어진 원소값들을 할당해주기 위한 배열을 선언해주었고

prefix_sum이라는 구간별 누적합(구간합)을 할당해주기 위한 배열을 선언해주었다. 

 

 

for i in range(1, N+1):
  for j in range(1, N+1):
    prefix_sum[i][j] = arr[i-1][j-1] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]

다음은 prefix_sum에 구간별로 누적합을 할당해주었다. 

여기 부분이 처음에는 뭐랄까 머리로 이해는 되는데 index랑 결합하면서 일반화해서 작성하려고하니까

복잡하기도하고 어려워서 종이에 써가면서 작성했다. 

 

 

이런 느낌으로....? ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

글로 작성하는게 이해가 될지는 모르겠지만 작성한 코드인

prefix_sum[i][j] = arr[i-1][j-1] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]

를 말로 설명해보자면

prefix_sum[i][j] 를 채워넣기 위해서 하나하나 처음 원소들부터 더해넣는 것이 아니라

이미 구해서 할당된 이전 인덱스의 구간합들을 이용하는 것인데 

새로 더해저야 할 값을 arr[i-1][j-1]에서 가져오고, 

이전에 더해서 구해놓은 값들을 prefix_sum[i-1][j] 와 prefix_sum[i][j-1]을 이용해 가져온다.

이때 둘을 더하면서 특정 겹치는 부분이 생기기때문에 prefix_sum[i-1][j-1]의 값을 빼주었다.

(글만으로 설명이 될지 모르겠는데 위에 그림을 그냥 말로 풀어쓴거다)

 

 

for _ in range(M):
  x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
  ans = prefix_sum[x2][y2] - prefix_sum[x1-1][y2] - prefix_sum[x2][y1-1] + prefix_sum[x1-1][y1-1]
  print(ans)

다음으로는 문제가 원하는대로 출력값을 

구간합에서 뽑아내어 출력해주면 된다.

이 부분 역시 바로 이해가 안되어서 그림을 그리고 

아래 다른 블로그의 설명을 참고해서 코드를 작성하였다.

https://yiyj1030.tistory.com/489

[알고리즘] 부분합, 누적합 (Prefix Sum) 쉽게 알아보기(파이썬)