https://www.acmicpc.net/problem/10986
공부 날짜 : 2023.01.30
정답 참조 여부 : X
2차 행렬의 누적합 중에서 k로 나누어 떨어지는 수의 개수를 구하는 문제이다.
2015번 수들의 합4와 매우 비슷한 문제이다.
어제 문제를 풀었기 때문에 어렵지 않게 풀 수 있었다.
로직은 k로 나눈 나머지가 이전의 누적합으로 있어서 뺄 수 있다면 답을 추가하는 방식이었는데
고민했던 부분이 주어진 값중 음수가 있는 경우이다.
음수가 있다면 k로 나눈 나머지가 이전에 누적합으로 있어도 뺄 수 없는 경우가 있다.
ex) 현재 누적합이 3 k가 2일때 이전 누적합이 5인 경우
이런 경우의 수도 생각해 봤지만 문제에서 친절하게 (0 ≤ Ai ≤ 109) 조건이 있어서 이전 로직 그대로 문제를 풀 수 있었다.
어제 푼 문제와 너무 유사해서 배운게 없다.
소스코드
import sys
input = sys.stdin.readline
###########################################
n, k = map(int, input().split())
input_data = list(map(int, input().split()))
sum_list = [0 for _ in range(1000)]
sum_list[0] = 1
# for i in range(0, 1001, k):
# sum_dict[i] = 1
sum_ = 0
answer = 0
for i in input_data:
sum_ += i
answer += sum_list[sum_ % k]
# 누적 합 딕셔너리 갱신
sum_list[sum_ % k] += 1
print(answer)
