[Python] 백준11660 구간 합 구하기 5

21 May 2023 in Study on Algorithm

백준11660 구간 합 구하기 5 링크

문제

예제 입력

---

코드

# 리스트 복사
# list2 = list1[:]
# list2 = list(list1)
# list2 = list1.copy()
# list2 = [] + list1

import sys

n, m = map(int, input().split())

arr = []
for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))

dp = [ [0] * (n+1) for _ in range(n+1)] 
for i in range(1, n+1): # 0 ~ 3
    for j in range(1, n+1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i - 1][j - 1]


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

설명

파이썬을 통해서 사용자로부터 입력받아 dp알고리즘을 사용하여 구간 합 구하기 5를 구현했습니다.

---

정리

# 리스트 복사
list2 = list1[:]
list2 = list(list1)
list2 = list1.copy()
list2 = [] + list1

    sum = 0 # 시간초과
    for i in range(x1-1, x2):
         for j in range(y1-1, y2):
             sum += arr[i][j]
    print(sum) 

처음에는 리스트를 복사하여 질문마다 계산하여 시간초과가 발생했습니다.

---

결과