10986. 나머지 합

문제

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

10986번: 나머지 합

 

이해

• 구간의 합을 구해야하는 문제이므로 누적 합 알고리즘을 활용한다.
• N의 범위가 100,000이므로 O(N)만큼 활용할 수 있고, 탐색을 통해 선택해야 하므로 이분 탐색이나 투포인터를 활용해야한다.
• 배열 값의 범위가 1,000,000,000이므로 이를 매번 다루면 연산 시간으로 인해 시간 초과가 염려되니, M으로 나눈 나머지 값을 가지고 활용한다. (최대 1,000,000,000 → 최대 1,000,000)
• 두 인덱스를 두고, 각 인덱스의 나머지값이 같으면 두 값의 차이는 M의 배수가 된다.
  • 예를들어 각 인덱스 값이 [5, 9]라고 했을 때 M = 4이면, 나머지는 [1, 1]이고, 두 값의 차는 4로 M으로 나누어 떨어진다.
• 따라서 나머지 값이 같은 인덱스 개수를 세고, 그중 2개를 고르는 경우의 수이다.
• 단, 나머지가 0인 경우, 첫번째부터의 누적합이므로 더해줘야 함

구현

1. 누적 합 구하기
   

   for i in range(1, N):
       arr[i] = arr[i] + arr[i-1]​

2. 나머지의 개수 구하기
   

   from collections import defaultdict
   # define
   remain = defaultdict(int)
   
   # 나머지의 개수 세기
   remain[arr[0]%M] += 1
   for i in range(1, N):
       remain[arr[i] % M] += 1

3. 2개를 뽑는 경우의 수 계산
   
   • n개중 k개를 고르는 조합 식: nCk = n! / {(n-k)!k!}
   • n개중 2개를 고르는 조합 식: nC2 = n(n-1) / 2
   • 나머지가 0인 요소들은 기본적으로 0번째부터의 누적합이므로 더해줘야함

     # 나머지 개수 중 2개 뽑아서 더하기(조합)
     ans = remain[0]
     
     for cnt in remain.values():
     
         ans += cnt * (cnt-1) // 2

 

코드

# 10986 나머지 합
import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
	# 입력
    N, M = map(int, input().split())
    arr = list(map(int, input().split()))
    
    # define
    remain = defaultdict(int)
	
    # 나머지의 개수 세기
    remain[arr[0]%M] += 1
    for i in range(1, N):
        arr[i] = arr[i] + arr[i-1]
        remain[arr[i] % M] += 1
    
    # 나머지 개수 중 2개 뽑아서 더하기(조합)
    ans = remain[0]
	
    for cnt in remain.values():
        
        ans += cnt * (cnt-1) // 2
    
    # 출력
    print(ans)



if __name__ =="__main__":
    main()

 

참조

2024.04.02 - [Algorithm/개념] - [알고리즘] 누적합(Prefix Sum)

[알고리즘] 누적합(Prefix Sum)

느낀점

• 단순 누적합이라고 생각할 수 있지만, 조금 더 생각하면 수학을 더한 응용이여서 한 번 더 생각해야 풀 수 있는 문제였다.
• n개 중 2개를 고를 때  n*(n-1)/2 로 간단하게 구할 수 있어 나중에도 자주 사용할 수 있을 것 같았다.
• 두 용액과 유사한 문제였지만, 투 포인터를 사용하지 않고도 풀 수 있어 좋은 경험을 쌓았다.