11660

날짜 : 2023. 02. 09

사용 언어 : python

 

문제

 

 

코드

import sys

n, m = map(int, sys.stdin.readline().split()) # 그래프 크기, 테스트케이스
graph = list()
# 그래프 입력
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))
total = [[0] * n for i in range(n)]  # 누적합

for i in range(n):
    temp = 0
    for j in range(n):
        temp += graph[i][j]
        total[i][j] = temp

"""for i in total:
    print(i)"""

for _ in range(m):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
    sum, minus = 0, 0
    x1 -= 1
    x2 -= 1
    y1 -= 1
    y2 -= 1
    for i in range(x1, x2+1):
        sum += total[i][y2]
        if (y1-1) >= 0 : minus += total[i][y1-1]
    res = sum - minus
    print(res)

 

 

풀이

- 누적합을 계산한 2차원 리스트를 만든 후 조건에 따라 가감하면서 문제를 풀이한다.

- (x1, y1) (x2, y2)의 값을 입력받고 제외해야 하는 값을 적절하게 제외한다.

 

 

알게된 점

- 처음 문제를 풀 때는 단순 이중 for문을 활용해서 풀었지만 당연하게도 TLE가 발생했다.

- 그래서 혹시나 하는 마음에 누적합(DP)를 이용해 문제를 풀이하는게 맞나 확인한 결과 역시나.

- 누적합을 계산한 그래프를 만들고, 입력받을 값들에 따라 달라지는 것들을 적용하여 문제를 풀이했다.

- DP 문제는 확실히 채점시간이 오래걸려 심장이 쫄깃해진다.

 

 

참고 사이트

-