백준 10986 - 나머지 합

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

10986번: 나머지 합

 

 

위 문제는 냅다 구현해버리면 이중 반복문을 사용하게 되어 시간 복잡도가 O(N^2)이 되므로 시간 초과가 나온다.

 

시간 초과 풀이)

n, m = list(map(int, input().split()))
nums = list(map(int, input().split()))
s = []
tmp = 0
cnt = 0
for i in range(len(nums)):
    tmp += nums[i]
    s.append(tmp)

for i in range(len(nums)):
    for j in range(i, len(s)):
        if s[j]%m==0:
            cnt += 1
    s = [a-nums[i] for a in s]

print(cnt)

위 알고리즘은 누적합을 이용했는데, 

누적합을 s리스트에 저장하고, i번째 탐색이 끝날 때마다 전체 누적합 리스트에서 i번째 원소를 빼줌으로써 i번째 수를 제외한 누적합으로 초기화 해주었다. 

 

질문 게시판을 보니 O(N^2)의 시간 복잡도를 가지면 계속 시간 초과로 실패한다고 하여 구글링하여 풀었다..

 

이제부터는 냅다 구현하기보다는 어떻게 구현해야 더 작은 시간 복잡도를 가질 수 있을지를 고려한 풀이가 필요하다.

 

 

 풀이 코드는 아래 포스팅을 참고하였다.

https://smhope.tistory.com/380

 

 

풀이코드)

n, m = list(map(int, input().split()))
nums = list(map(int, input().split()))
s = 0
remainder = [0]*m # 각 나머지를 갖는 수의 갯수를 저장할 리스트

for i in range(len(nums)):
    s += nums[i] # 누적합
    remainder[s%m] += 1 # 해당 나머지를 갖는 수의 갯수를 1증가

result = remainder[0] # 나머지가 0인 모든 수는 카운트해야함

for i in remainder:
    result += i*(i-1)//2  # i개 중에서 2개를 택할 경우의 수 (조합 iC2)

print(result)

 

위 알고리즘은 나머지가 같은 수끼리 빼주면 나머지가 0으로 나누어 떨어진다는 것을 이용한 것이다.

 

a라는 수를 m으로 나누었을 때 나머지 r

b라는 수를 m으로 나누었을 때 나머지 r

a = A*m + r

b = B*m + r

a-b = (A-B)*m ==> m으로 나누었을 때 나머지가 0으로 나누어 떨어진다.

두 수의 차이는 두 수 사이의 구간을 나타내며, 구간의 합에서 M으로 나누어 떨어지는 곳을 찾는 문제이므로 위 알고리즘을 적용하면 된다.

 

 

위 알고리즘 흐름은 다음과 같다.

1. m으로 나누었을 경우, 나올 수 있는 나머지는 0~m-1까지 이므로 크기가 m인 나머지 리스트를 선언한다.

2. 나머지 리스트를 remainder라고 했을 때, remainder[i]에는 나머지가 i인 수의 갯수가 저장된다.

3. 반복문을 돌며 누적합을 구하며 해당 누적합을 m으로 나누었을 때의 나머지를 remainder에 저장한다.

4. remainder[0]은 m으로 나누었을 때 정확히 떨어지는 숫자의 갯수이므로 그대로 result에 넣는다.

5. 나머지 리스트 remainder을 반복문을 돌면서 해당 나머지를 갖는 숫자가 n일 경우 n개 중에서 2개를 택할 경우의 수를 2개 택하는 경우의 수를 계산하여 result에 더한다. (조합)