파이썬 나머지 합(백준 BOJ 10986)
2022, Oct 09
문제
수 N개 A1, A2, …, AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + … + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, …, AN이 주어진다. (0 ≤ Ai ≤ 109)
출력
첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.
예제 입력 1
5 3
1 2 3 1 2
예제 출력 1
7
📝 풀어보기
📌 수의 개수 N, M으로 나누어 떨어지는 수 를 입력받는다.
N개의 수를 리스트 형태로 입력받고 리스트의 끝에 0을 추가한다.
M개의 개수만큼 0을 추가해서 cnt 리스트에 담는다.
N, M = map(int, input().split()) # 5 3
# 맨 끝에 0을 넣는 이유?
# 누적합을 구할 때 A[i-1]로 맨 끝을 누적하기때문에
A = list(map(int, input().split())) + [0] # 1 2 3 1 2
cnt = [0] * M # [0, 0, 0]
📌 N만큼 반복하면서 누적합을 구한다. 구한 누적합을 M으로 나눈 나머지가 같은것끼리 분류하고 나머지가 같은것들을 값을 1씩 증가시킨다. 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 ans에 저장한다.
for i in range(N): # 0 1 2 3 4
# 1. 누적합을 구한다
# 1 3 6 7 9
A[i] += A[i-1]
# 2. 누적합을 M으로 나눈 나머지가 같은 것끼리 분류
# 1%3 = cnt[1], 3%3 = cnt[0], 6%3 = cnt[0], 7%3= cnt[1], 9%3 = cnt[0]
# cnt = [3, 2, 0]
cnt[A[i] % M] += 1
ans = cnt[0] # 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수
📌 cnt에서, 누적합의 나머지가 같은 것들 중 2개를 조합한다. 누적된 조합값을 출력한다.
for i in cnt: # 3 2 0
# 누적 합의 나머지가 같은 것들 중에서 2개를 조합한다.
ans += i * (i-1) // 2
print(ans)
전체 코드
N, M = map(int, input().split()) # 5 3
# 맨 끝에 0을 넣는 이유?
# 누적합을 구할 때 A[i-1]로 맨 끝을 누적하기때문에
A = list(map(int, input().split())) + [0] # 1 2 3 1 2
cnt = [0] * M # [0, 0, 0]
for i in range(N): # 0 1 2 3 4
# 1. 누적합을 구한다
# 1 3 6 7 9
A[i] += A[i-1]
# 2. 누적합을 M으로 나눈 나머지가 같은 것끼리 분류
# 1%3 = cnt[1], 3%3 = cnt[0], 6%3 = cnt[0], 7%3= cnt[1], 9%3 = cnt[0]
# cnt = [3, 2, 0]
cnt[A[i] % M] += 1
ans = cnt[0] # 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수
for i in cnt: # 3 2 0
# 누적 합의 나머지가 같은 것들 중에서 2개를 조합한다.
ans += i * (i-1) // 2
print(ans)