[백준] 10986 나머지

Hyun·2024년 3월 16일

백준

목록 보기

58/81

문제

수 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으로 나누어 떨어지는 구간의 개수를 출력한다.

예제 입력

5 3
1 2 3 1 2

예제 출력

풀이

이 문제에 시간을 5시간 정도 쓴 것 같다. 아무리 해도 O(NM) 보다 더 줄일 수 있는 방법을 생각할 수 없었다. 그래서 타 풀이를 참고했다. 고민한 과정을 알아보자..

첫번째 풀이(구간별 누적합 반복 계산)

수가 N개이므로 구간을 1,2,...,N으로 나눠서 각각의 구간에 대해 누적합을 계산하면서 M으로 나눈 나머지가 0으로 떨어질 경우를 계산하였다. 일반적인 구간 누적합 문제를 구간을 1부터 N까지의 경우에 대해 반복한 풀이이다.

n,m = map(int,input().split())
arr = list(map(int,input().split()))
cnt = 0
for i in range(1,n+1): # 구간을 1,2,...,n 으로 각각 테스트
    v = sum(arr[0:i]) # 제일 앞 i개의 합
    if v % m == 0: cnt+=1
    for j in range(i, n):
        v = v + arr[i]-arr[i-i]
        if v % m == 0: cnt+=1
print(cnt)

시간복잡도 O(NM)

두번째 풀이(구간별 누적합을 하나의 배열에서 관리)

하나의 배열을 사용하여 구간별 누적합을 저장한다. 예를 들어 arr[0] 은 현재 숫자 하나만의 누적합이고, arr[1] 은 현재 숫자~직전 숫자의 누적합, arr[k]는 현재 숫자~거리가 k만큼 떨어진 숫자까지의 누적합이다.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
lst = list(map(int,input().split()))
arr = []
cnt = 0

for num in lst:
    arr.insert(0,num)
    if num % m == 0: cnt+=1
    for i in range(1,len(arr)):
        arr[i]+=num
        if arr[i] %m == 0: cnt+=1
print(cnt)

시간복잡도 O(NM)

세번째 풀이(불필요한 누적합 저장X)

누적합이 M으로 나누어 떨어지는 경우는 누적합 배열에 저장하지 않는다. 구간별 누적합의 저장 순서는 상관없기 때문이다. 누적합이 M으로 나눠 떨어지는가만 알면 된다.

그리고 나머지를 저장해도 동일하기 때문에 누적합 대신 누적합의 나머지를 저장한다.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
lst = list(map(int,input().split()))
arr = []
cnt = 0

for idx, num in enumerate(lst):
    subarr = []
    if num % m != 0: subarr.insert(0,num%m) # 나머지가 0이 아닌 경우 저장 
    for i in range(0,len(arr)):
        v = (arr[i]+num) % m 이전 누적합에서 현재값 더했을때 
        if v != 0: subarr.append(v) # 나머지 0이 아닐때만 저장
    for j in range(idx-len(arr)): # 이전에 비어있던 공간의 수(나머지0인 경우)
        if num % m != 0: subarr.append(num%m) # 현재 값과 더했을때 나머지 0이 아닐때만 저장
    # 이렇게 하면 지금 subarr 에 비어있는 여백은 다 나머지가 0인 경우임
    cnt += idx+1-len(subarr) # 여백의 공간만큼 cnt에 더해줌
    arr = list(subarr) 
print(cnt)

그래도 시간복잡도 O(NM), 이 풀이에서도 시간초과가 발생해서 더 이상 이렇게 누적합의 저장 공간을 줄이는 건 소용이 없다고 판단해서 타 풀이를 참고하게 되었다.

네번째 풀이(나머지 성질 이용&조합 이용)

나머지가 같은 두 구간의 합을 빼면 나머지가 0이라는 사실을 이용한다. 따라서 나머지가 같은 구간의 개수를 구한 다음 조합을 이용해 2개를 선택하면 된다.

예를 들어, 나머지에 따른 누적합 구간의 개수가 나머지 0: 3개, 1: 2개, 0: 1개 인 경우 나머지가 그 자체로 0인 구간 3개 + 나머지가 0인 구간들에서 2개를 선택 + 나머지가 1인 구간들에서 2개를 선택 하여 합을 계산하면 된다.

n,m = map(int,input().split())
arr= list(map(int,input().split()))
dic={}
s = 0
cnt = 0

for i in range(0,len(arr)):
    s = (s+arr[i])%m
    if s in dic: dic[s]+=1
    else: dic[s]=1
for k,v in dic.items():
    cnt += v*(v-1)//2
if 0 in dic: cnt+=dic[0]
print(cnt)