004 구간 합 구하기 5

첫번째 코드

 

누적합을 이용하자!

0열에 이전 행의 마지막 열의 값을 추가하여 인덱싱 문제를 해결하자!

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
number = []
interval = []

for i in range(n):
    number.append(list(map(int, input().split())))

for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    interval.append((x1-1, y1-1, x2-1, y2))

# 누적합 데이터 만들기
before_row_cumul = 0
for i in range(0, n):
    number[i].insert(0, before_row_cumul)
    for j in range(1, n+1):
        number[i][j] += number[i][j-1]
        before_row_cumul = number[i][j]

for i in range(m):
    end = number[interval[i][2]][interval[i][3]]
    start = number[interval[i][0]][interval[i][1]]

    answer = end - start
    print(answer)

오답...?

문제 이해에 오류가 있었다!!

문제는 오른쪽과 같이 시작과 끝 위치의 사각형 내 숫자들을 더한 값을 구하는 것인데,

나는 시작을 기준으로 끝까지의 숫자들을 더한 값을 구한 코드이다!!!!

 

그러면 흠...사각형에 있는걸 구하는 방법은..?

---

두번째 코드

 

책에서 배운 내용으로 누적합을 구하고 인덱싱하는 방법으로 하면 용량이 줄어드니까 그렇게 하기로 한다!!

근데 문제는

1. 어떻게 박스 누적값을 더하여 표현하지?

2. 박스 누적값에서 인덱싱 하면 어떻게 구하지?

 

해결책은 똑같았다!!!

1. 박스의 누적값 구하는 방법

맨 우측 아래의 누적합 값을 구하기 위해 빨간색과 파란색을 더하고 두번 더해진 부분인 연두색을 뺀다!

그럼 위와 같이 검정 부분이 구해진 것인데, 거기에 보라색만 더하면 우측 아래의 누적합 값이 나온다!!

 

D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1]

 

2. 박스 누적값에서 인덱싱하여 구하는 방법

1번의 시작과 끝이 주어진 경우이다.

전체 빨간 부분에서 파란색과 연두색을 뺀다!

그렇다면 두번 빠진 보라색을 한번 더하게 되면 인덱싱한 부분만 남게 된다!

 

D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][x2-1]

 

이런 아이디어를 갖고 코드를 작성하면 된다!

 

그리고 추가 팁은!!!

인덱싱에서 1부터로 되어 있기 떄문에 A 리스트의 0행과 0열에 모두 0을 채워 넣으면 인덱싱 값 숫자를 그대로 사용할 수 있으므로 헷갈릴 일이 없다!

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
A = [[0]*(n+1)]
D = [[0]*(n+1) for _ in range(n+1)]

for i in range(n):
    a_row = [0] + [int(x) for x in input().split()]
    A.append(a_row)

for i in range(1, n+1):
    for j in range(1, n+1):
        D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    answer = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(answer)

 

<pseudocode>

n 리스트 크기, m 질문 수

A 원본 리스트, D 합 배열

 

for n만큼 반복:

    원본 리스트 데이터 저장

 

for i in 1부터 n까지 반복:

    for j in 1부터 n까지 반복:

        합 배열 저장

        D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]

 

for _ in m만큼 반복:

    질문에 대한 결과 계산 및 출력

    answer = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/11660.%E2%80%85%EA%B5%AC%EA%B0%84%E2%80%85%ED%95%A9%E2%80%85%EA%B5%AC%ED%95%98%EA%B8%B0%E2%80%855

programmers/백준/Silver/11660. 구간 합 구하기 5 at main · ornni/programmers