[10986] 나머지 합 구하기 #python #백준

	백준 문제풀이		python
			No. 10986 나머지 합 구하기

 

 

#python #백준 #문제풀이 #10986 나머지 합 구하기

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

10986번: 나머지 합

 

예제 입력 1

5 3
1 2 3 1 2

예제 출력 1

7

 

 

 

이번 글에서는 구간의 합으로 나누는 법을 구현하는데 중점을 둔다. (A+B) %C 는 (A%C)+(B%C)) %C 와 같다. 

 

---

// 알고리즘

가장 중요한 목적이 무엇인지?

구간의 합으로 계산하려면 어떻게 해야하는지?

예시로

5 3
1 2 3 1 2

입력 값이 들어오고 3으로 나누어 떨어지는 쌍을 나누었더니 7개가 나온다.

여기서 i<=j 이므로 하나도 포함.

 

(1,2)[0.1] (1,2,3)[0,2] (1,2,3,1,2)[0,4]

(2,3,1) [1,3]

(3) [2]

(3,1,2) [2,4]

(1,2) [3,4]

 

이런식이므로, 일단 더해가면서 어라? 이게 안 나눠떨어지네 하면 가차없이 다음 정렬로 돌리면 된다.

 

왠지 N이 10^6이라서 1초를 넘는 시간 복잡도가 걸릴 거 같지만 (logN^2이면 100초가 걸린다고 하는데)

좋은 방법이 있을까?

 

부분합을 모두 구해두고.

적절하게 빼주었을때, 어떻게 빼야 부분합이 나누어 떨어질까?

부분합이 배수로 애초에 나뉜다면?

[1, 3, 6, 7, 9]

3,6,9 가 되겠다. 이는 [0:]에서 이어진 경우.

7-1=6 이 되겠다 이는 [1:3]인 경우.

 

버블 정렬로 빼면 나오게 된다. 버블정렬 써도 되나?

암튼 해본다.

 

역시 시간초과

 

(A+B) %C 는 (A%C)+(B%C)) %C 와 같다. 는 아이디어가 중요하다.

 

해당 부분합들을 %M 으로 나누면 0이면. 나뉘어서 계산되는 것이다. 더해서 M이되면? 역시 계산 되는 것이다. 

[1, 0, 0, 1, 0]

 

 

그리고 부분합이 같은 값 을 골라서 빼면 0이 나오므로 조합을 구하면 된다.

index 0과, index 4의 1을 빼면 어떤 결과인지 알아보자.

index 0 의 값은 1

index 3의 값은 1,2,3,1 의 값이다. 어차피 나머지 연산이라 뒤의 값이 사라지고 중복값을 빼준것. 따라서 [1:3]

 

 

 

 

왜 이런 방법을 선택했는지?

 

 

---

// 계획하기

	함수명	설명
1.
2.
3.

 

---

// 구현하기

-> How?

어떻게 구현?

 

첫째 줄에 N과 M이 주어진다.

그리고 M의 합으로 나누어 떨어지는 쌍의 개수를 구해야한다.

 

 

->Why?

왜 이런 방법을?

---

// 수정하기

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
numbers = list(map(int, input().split()))
prefix_sum = []
temp = 0
cnt = 0

for i in numbers:
    temp = temp+i
    prefix_sum.append(temp)
    if(temp%M == 0): cnt+=1

# for i in range(M):
#     print(prefix_sum[e] - prefix_sum[s-1])

#print(prefix_sum)

for i in range(len(prefix_sum)):
    for j in range(len(prefix_sum)-1,i,-1):
        if (prefix_sum[j]-prefix_sum[i]) % M == 0:
            cnt+=1
print(cnt)

 

버블 정렬이라 시간초과, 저기서 temp%M ==0 저기서 아이디어를 얻었어야 했다.

 

 

---

// 완성코드

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
numbers = list(map(int, input().split()))
prefix_sum = []
remainder = [0]*M
temp = 0
cnt = 0

for i in numbers:
    temp = (temp+i)%M
    if(temp == 0): cnt+=1
    prefix_sum.append(temp)
    remainder[temp] += 1

for i in range(M):
    if remainder[i]>1:
        cnt += (remainder[i]*(remainder[i]-1) //2)
print(cnt)