Baekjoon11660 - 구간 합 구하기 5 (Python)

백준 사이트 11660 - 구간 합 구하기 5 문제입니다.

이 글을 보시기 전에 문제를 풀기 위해 충분한 생각을 하셨나요? 답을 안 보고 푸는게 최대한 고민하는게 가장 중요하다고 생각합니다.!!

☑️ 1. 문제

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

---

☑️ 2. Input , Output

---

☑️ 3. 분류 및 난이도

solved.ac class 4 문제입니다.

---

☑️ 4. 생각한 것들

• 수학 + DP문제입니다.
• 크게 어렵지 않습니다. 어떻게 시간을 줄일 수 있을지가 관건인 문제입니다.
• 입력을 받는데, 기존 맵은 쓰일 일이 없고 그들의 합이 쓰일테니까 그들의 합으로 초기화 해줍니다.
• 행과 열이 정해져있으면 항상 그 구간의합 모양은 맵에서 봤을때 사각형이므로 가로 세로를 어떤방식으로 구할지 생각만 하면 됩니다.

---

5. code

from sys import stdin


def row_sum(row: list) -> list:
    for i in range(1, len(row)):
        row[i] += row[i - 1]
    return row


def solution() -> None:
    n, m = map(int, stdin.readline().split())
    maps = []
    for i in range(n):
        row = list(map(int, stdin.readline().split()))
        row = row_sum(row)
        maps.append(row)
    for j in range(m):
        x1, y1, x2, y2 = map(int, stdin.readline().split())
        result = 0
        for x in range(x1 - 1, x2):
            if y1 - 2 < 0:
                result += maps[x][y2 - 1]
            else:
                result += maps[x][y2 - 1] - maps[x][y1 - 2]
        print(result)


solution()

---

6. 후기

• 이문제를 토대로 Gold1 달성

c++로 작성이 필요하거나 도움이 필요하시면 댓글을 작성해주세요.!! 기록용이라 설명이 자세하지 않습니다.