python 11660 구간 합 구하기 5

📌 문제 정보

• 문제 번호: 11660
• 문제: https://www.acmicpc.net/problem/11660
• 난이도: 실버 1

---

🧩 문제 요약

• 크기 N×N인 2차원 배열이 주어짐
• M개의 쿼리에 대해, 각 쿼리는 (x1, y1)부터 (x2, y2)까지의 부분 합을 구해야 함
• 쿼리는 1-based index로 주어짐
• 시간 제한 내에 모든 쿼리를 빠르게 처리해야 함

---

🧪 예제 입력 / 출력

예제 입력

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

 

 

예제 출력

27  
6  
64

 

 

설명

• 첫 번째 쿼리: (2,2)부터 (3,4)까지의 합 = 3+4+5 + 4+5+6 = 27
• 두 번째 쿼리: (3,4) 하나만 선택됨 = 6
• 세 번째 쿼리: 전체 합 = 64

---

💡 접근 방식

• 단순히 쿼리마다 반복문으로 구하면 시간 초과 발생
• 누적합(2차원 prefix sum) 이용해 한 번의 쿼리를 O(1)로 처리 가능
• 이를 위해 먼저 입력 배열에 대해 누적합 테이블을 구성해야 함

---

⚙️ 알고리즘 설명

• 2차원 누적합 sums[i][j]는 (1,1)부터 (i,j)까지의 합을 의미함
• 점 (x1, y1)부터 (x2, y2)까지의 부분합은 아래 공식으로 계산 가능:

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

• 위 공식은 Inclusion-Exclusion 원리를 활용한 것임

---

🧑‍💻 코드 구현 (Python)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = [list(map(int, input().split())) for _ in range(N)]

# 누적합 테이블 초기화 (1-based 인덱스)
sums = [[0] * (N + 1) for _ in range(N + 1)]

# 누적합 계산
for i in range(1, N + 1):
    for j in range(1, N + 1):
        sums[i][j] = (
            sums[i][j - 1] + 
            sums[i - 1][j] - 
            sums[i - 1][j - 1] + 
            nums[i - 1][j - 1]
        )

# 쿼리 처리
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    result = (
        sums[x2][y2]
        - sums[x1 - 1][y2]
        - sums[x2][y1 - 1]
        + sums[x1 - 1][y1 - 1]
    )
    print(result)

---

🔁 다른 풀이 / 코드 개선 방향

• 입력 배열이 크지 않기 때문에 numpy 사용 시 코드 간결해질 수 있음
• 파이썬 외에도 C++ 등에서 scanf와 같은 빠른 입력 방식 사용하는 것이 유리함

---

⏱️ 시간복잡도 분석

• 누적합 배열 계산: O(N²)
• 각 쿼리 처리: O(1)
• 전체 시간복잡도: O(N² + M)
• 메모리: O(N²)

---

📝 결론 및 팁

• 2차원 배열 누적합은 다양한 문제에서 응용 가능함
• 꼭 외워두면 좋음 (특히 Inclusion-Exclusion 공식)
• 유사 문제 풀어보며 익숙해지는 것 추천

유사 문제 추천

• 11659 구간 합 구하기 4: https://www.acmicpc.net/problem/11659
• 14427 수열과 쿼리 15: https://www.acmicpc.net/problem/14427