백준 나머지합 파이썬

문제

예제로

입력

5 3

1 2 3 1 2

출력

7

이주어졌다

 

첫번째 아이디어

수가 주어졌을때

그수로 만들수있는 모든 조합을 구한다 (구간을 구하는것이니 요소숫자는 2이다)

그조합의 합이 만약 M으로 나누어 떨어진다면 ans의 개수를 하나 올린다

 

첫번째 아이디어에 누적합기능을 추가하면

구간합을 구할때 더 빠르게 할수있다 이것을 구현해보자

 

조합을 이용해서 구간의 넓이가 2이상인 모든 구간의 경우를 계산하고

구간의 길이가 1인경우에는 또 따로 조사를 해서 나눠떨어질경우 더했다

구현후 제출

from itertools import combinations
N, M=map(int, input().split())
la=list(map(int, input().split()))
print(la)
# 누적합 리스트 만들기
sumed_list=[0]
sumed_num=0

for i in range(N):
    sumed_num+=la[i]
    sumed_list.append(sumed_num)

ans=0
for i in combinations(list(range(1,N+1)), 2):
    if (sumed_list[i[1]] - sumed_list[i[0]-1]) % M == 0:
        ans+=1
for i in la:
    if i%M==0:
        ans+=1

print(ans)

출력초과가 떳다 

print(la)를 지우고 다시 제출해본다

from itertools import combinations
N, M=map(int, input().split())
la=list(map(int, input().split()))
# 누적합 리스트 만들기
sumed_list=[0]
sumed_num=0

for i in range(N):
    sumed_num+=la[i]
    sumed_list.append(sumed_num)

ans=0
for i in combinations(list(range(1,N+1)), 2):
    if (sumed_list[i[1]] - sumed_list[i[0]-1]) % M == 0:
        ans+=1
for i in la:
    if i%M==0:
        ans+=1

print(ans)

우리들의 친구 시간초과가 떳다

 

1퍼센트도 뜨지못한걸보면 굉장히 느린것같다

 

그렇다 가능한 모든 구간을 일일이 검사해본다는거 자체가 사실 시간초과의 냄새가 훌훌나긴했다

모든구간을 조사하는 방법은 틀렸다

 

그렇다면 어떻게 푸는것일까

 

모르겠다 답을 보기로 한다

출처

모든 구간의 합은 sumed_list의 요소중 2개를 선택해 뺄셈으로 구할수있다

이때 나머지가 같은것끼리빼면 나누어 떨어진다는 사실을 알게되었다

 

나머지가 1로 같은 7과 4를 빼면 3으로 나누어떨어진다

 

즉 나머지가 같은 요소끼리묶어 그 수들로 만들수있는 조합의 개수들을 각각 더하면 답이 되는것이다

 

구현후 제출

from itertools import combinations

def fac(x):
    ans=1
    for i in range(1,x+1):
        ans=ans*i
    return ans

def comb_num(n,r):
    return ( fac(n) ) // ( fac(n-r) * fac(r) )

N, M=map(int, input().split())
la=list(map(int, input().split()))
# 누적합 리스트 만들기
sumed_list=[0]
sumed_num=0

for i in range(N):
    sumed_num+=la[i]
    sumed_list.append(sumed_num)

# 나머지로 구성된 새로운 sumed list
for i in range(N+1):
    sumed_list[i]=sumed_list[i]%M

ans=0
for i in range(M):
    count=0
    for j in sumed_list:
        if i==j:
            count+=1
    ans+=comb_num(count,2)
print(ans)

근데 또 시간초과가 떳다 켁...

 

다른분 답을 더 자세하게 읽어본다

나는 많은곳에서 습관적으로 시간낭비를 했다는 사실을 깨달음

 

첫번째로 나는 나머지를 하나씩 구할때마다 sumed_list전체 요소를 훑어보았다

따라서 시간복잡도는 M*N이다

 

그런데 그렇게 할필요없이 N의 시간복잡도만에 끝낼수있다

remain_list라는 나머지를 담는 리스트를 만드는데 인덱스가 나머지값의 의미를 갖는다

sumed_list를돌면서 나머지에 해당하는 remain_list 인덱스 요소에 +=1을 해준다

 

또한 조합을 구하는 방법역시 팩토리얼을 이용한 복잡한 방법이 필요없이

나머지개수가 i라고 했을때

i*(i-1)//2 로 간단하게 구할수있었다

저보기좋게 만들어놓은 공식대로 팩토리얼을 두개나 구하게 되면 수가 커졌을때 시간이 매우많이걸리게될것이 분명하다

 

뿐만아니라 누적합 리스트를 만드는과정, 누적합리스트의 각 요소들을 M으로 나눴을때 나머지를 구하는 과정 그리고 

그나머지들을 각각 remain_list로 보내서 count하는 과정을 for문 하나로 끝낼수있다

 

생각보다 고칠점이 많아서 놀랐다

 

구현후 제출하였다 

N, M=map(int, input().split())
la=[0]+list(map(int, input().split()))
remain_list=[0 for i in range(M)]
sumed_num=0
for i in range(N+1):
    sumed_num+=la[i]
    remain_list[sumed_num%M]+=1

ans=0
for i in remain_list:
    ans+=i*(i-1)//2
print(ans)

맞았다