[백준] 11660번 : 구간 합 구하기5

문제

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

풀이

[백준] 11660번 : 구간 합 구하기5 🥈(실버 1)
🎯 44.539%
⏰ 걸린 시간 : 시간초과
⏲ 시간복잡도
구간 합 O(n)

• 알고리즘 유형 : [구간 합]

📚 [구간 합]

✅ 풀이방법 & 구간 합 알고리즘로 푼 이유?
0. 구간 합을 먼저 구해놓는게 관건이다.
1. N^2으로 구해버리면 시간초과가 발생하기 때문이다.
2. 구간합을 쓰지않고 그때마다 결과를 탐색하게 하면 시간초과가 발생한다.

코드(code)

import sys
input=sys.stdin.readline
N, M = map(int, input().split())
graph = [[0]* (N+1)]
# print(graph)
for i in range(1,N+1):
    arr =[0]+ list(map(int,input().split()))
    graph.append(arr)

# print(graph)
# 열 누적 
for x in range(1,N+1):
    for y in range(2,N+1):
        graph[x][y] += graph[x][y-1]

# 행 누적 
for x in range(2,N+1):
    for y in range(1,N+1):
        graph[x][y] += graph[x-1][y]
# print(graph)

# [[0, 0, 0, 0, 0], [0, 1, 3, 6, 10], [0, 3, 8, 15, 24], [0, 6, 15, 27, 42], [0, 10, 24, 42, 64]]
for tc in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    print(graph[x2][y2] - graph[x2][y1-1]- graph[x1-1][y2]+graph[x1-1][y1-1])

회고

2차원 배열에서 접근하는건 조금 까다로웠다 오답하면서 학습할 것.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/Prefix_Sum/11659(%EA%B5%AC%EA%B0%84%20%ED%95%A9%20%EA%B5%AC%ED%95%98%EA%B8%B04).py