BOJ(백준) 11660[구간 합 구하기 5]

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 11660번을 풀어보겠습니다. 이 문제는 주어진 2차원 배열에서 여러 쿼리에 대한 부분합을 구하는 문제입니다. 좌표 (x1, y1)부터 (x2, y2)까지의 합을 빠르게 계산할 수 있도록 누적합 배열을 사용하여 문제를 해결해보겠습니다.

 

1. 문제 설명

주어진 2차원 배열에서 여러 쿼리에 대한 부분합을 구하는 문제입니다. 좌표 (x1, y1)부터 (x2, y2)까지의 합을 빠르게 계산할 수 있도록 누적합 배열을 사용하여 문제를 해결합니다.

 

2. 접근법

1. 입력받기: 배열의 크기(N)와 쿼리의 개수(M)를 입력받습니다.

2. 그래프 입력받기: N x N 크기의 2차원 배열을 입력받습니다.

3. 누적합 배열 초기화: 누적합 배열(prefix sum 배열)을 초기화합니다.

4. 누적합 계산: 주어진 배열의 누적합을 계산합니다.

5. 부분합 계산: 각 쿼리에 대해 누적합을 이용하여 부분합을 빠르게 계산합니다.

6. 정답 출력: 각 쿼리에 대한 결과를 출력합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력받기
N, M = map(int, input().split())

# 그래프 저장을 위한 리스트 초기화
graph = []

# 그래프 입력받기
for _ in range(N):
    graph.append(list(map(int, input().split())))

# 누적합 배열 초기화 (prefix sum 배열)
prefix = [[0] * (N+1) for _ in range(N+1)]

# 누적합 계산
for x in range(N):
    for y in range(N):
        prefix[x+1][y+1] = prefix[x+1][y] + prefix[x][y+1] + graph[x][y] - prefix[x][y]

# 정답출력 변수 초기화
ans = [0] * M

# 주어진 좌표의 누적합 계산
for i in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    # (x1, y1)부터 (x2, y2)까지의 부분합 계산
    ans[i] = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]

# 정답 출력
for i in range(M):
    print(ans[i])

4. 코드 설명

 

1. 입력받기

• N과 M을 입력받아 배열의 크기와 쿼리의 개수를 설정합니다.

2. 그래프 입력받기

• N x N 크기의 2차원 배열을 입력받아 graph 리스트에 저장합니다.

3. 누적합 배열 초기화

• prefix 리스트를 사용하여 누적합 배열을 초기화합니다. 이 배열은 (N+1) x (N+1) 크기로 설정하여 인덱스 계산을 용이하게 합니다.

4. 누적합 계산

• 2차원 배열의 각 원소에 대해 누적합을 계산하여 prefix 배열에 저장합니다.

5. 부분합 계산

• 각 쿼리에 대해 누적합 배열을 이용하여 빠르게 부분합을 계산합니다. 이는 (x1, y1)부터 (x2, y2)까지의 합을 구하는 데 사용됩니다.

6. 정답 출력

• 각 쿼리에 대한 결과를 ans 리스트에 저장하고, 최종적으로 출력합니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_03_04_11660.py at main · pcy4196/coTest