[백준 11660번] 구간 합 구하기 5 (Python 파이썬) 풀이 방법

백준 11660번 <구간 합 구하기 5> 문제 보기

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

11660번: 구간 합 구하기 5

 

 

백준 11660번 <구간 합 구하기 5> 문제 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n, m = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]

graph = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
  for j in range(1, n+1):
    graph[i][j] = graph[i-1][j] + graph[i][j-1] - graph[i-1][j-1] + table[i-1][j-1]

for _ in range(m):
  x1, y1, x2, y2 = map(int, input().split())
  result = graph[x2][y2] - graph[x1-1][y2] - graph[x2][y1-1] + graph[x1-1][y1-1]
  print(result)

누적합을 이용한 풀이다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 라는 조건 때문에 다중 for문을 사용해 푼다면 시간 초과가 나기 마련이다. table 에 N*N 크기의 표를 입력받고, graph 에 누적합을 저장시켜주었다.

 

우리가 구해야 하는 범위 (x1,y1,x2,y2) 가 파란색 칸이라고 하면, (x2,y2) 의 누적합에서 일부를 빼주어야 한다.

 

이후, 두 번 계산된 부분을 다시 더해주면 원하는 범위의 누적합을 구할 수 있다.

 

 

 

첫 번째 도전

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n, m = map(int, input().split())
table = []
for _ in range(n):
  temp = list(map(int, input().split()))
  table.append(temp)

numbers = []
for _ in range(m):
  q = list(map(int, input().split()))
  numbers.append(q)

for i in range(m):
  result = 0
  array = numbers[i]
  for i in range(array[0]-1, array[2]):
    for j in range(array[1]-1, array[3]):
      result += table[i][j]
  print(result)

실버1 치고는 너무 쉬운 문젠데? 라는 의심은 괜한 것이 아니었다. 범위 M만큼 (x1, y1, x2, y2) 를 입력 받고 x2-x1 와 y2-y1 만큼 for 반복문을 돌렸더니 시간 초과가 떴다. 

 

 

너무 블로그 글 쓰려고 문제를 푸는 듯한 느낌이 나서 한동안 내 블로그를 들어오지 않았다. 그 부작용으로는 백준 문제를 푸는데에 집착했다는 것... 어디로든 좋은 방향이겠거니~ 그러려니~ 싶다. 곧 취준생인,, 나에게 조금 큰 꿈인 것 같지만 현재 일상을 브이로그로 살짝 남겨볼까 한다. 더 열심히 살게 되지 않을까 라는 생각이다 ㅎ