this.code();

🤫  solution_11659

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

prefix_sum = [0]
p_sum = 0
for i in num:
    p_sum += i
    prefix_sum.append(p_sum)


for _ in range(m):
    i, j = map(int, input().split())
    print(prefix_sum[j] - prefix_sum[i-1])

🤫  Algorithm 

🤫  solution_11660

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

S = [[0 for i in range(n + 1)] for i in range(n + 1)]

for i in range(n):
    for j in range(n):
        S[i + 1][j + 1] = (S[i][j + 1] + S[i + 1][j] - S[i][j]) + num[i][j]

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

부분 합 개념을 이용해서 풀 때, 부분 합을 계산한 배열을 i, j로 순차적으로 접근할 경우 
O(n^2)으로 시간 초과가 발생하므로 다른 풀이 방법이 필요하다.

🤫  Algorithm 

미리 구해둔 prefix sum에서의 부분합은 S[j] - S[i - 1]의 과정이다.

이때, S[j]와 S[i-1]이 각각 m으로 나눴을 때의 나머지가 동일하다면?
S[j] - S[i - 1] 연산 후 나머지는 0이 되기에 m으로 나눠 떨어진다.

결국 m으로 나눠떨어지는 부분합을 구하는 것은 
나머지가 동일한 idx 중 임의로 nC2를 선택하는 것과 같으므로 다음 알고리즘을 거친다.

[1] [2] [3] [1] [2] -> [0] [1] [3] [6] [7] [9] -> [0] [1] [0] [0] [1] [0] 
-> [0 : 4, 1 : 2] -> 6 + 1 -> 7

🤫  solution_10986

import sys
input = sys.stdin.readline

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

rest_list = [0 for _ in range(m)]
rest_list[0] = 1

prefix_sum = 0
for i in range(n):
    prefix_sum += num_list[i]
    rest = prefix_sum % m
    # 나머지 값에 따라서 idx 정보 저장
    rest_list[rest] += 1

cnt = 0
for i in rest_list:
    cnt += i*(i - 1) // 2

print(cnt)