[백준][누적합] 나머지 합

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

10986번: 나머지 합

 

내가 작성한 코드

import sys
from collections import Counter

read = sys.stdin.readline

def read_data():
    N, M = map(int, read().rstrip().split())
    arr = list(map(int, read().rstrip().split()))
    return N, M, arr

def get_modular_accu(arr, M):
    mod = Counter()
    accu = [arr[0]]
    mod[accu[-1] % M] += 1

    for num in arr[1:]:
        accu.append((accu[-1] + num) % M)
        mod[accu[-1] % M] += 1

    return mod

def get_answer(mod):
    answer = 0
    answer += mod[0]
    for n in mod.values():
        if n == 1:
            continue
        answer += int(n * (n-1) / 2)
    return answer


N, M, arr = read_data()
mod = get_modular_accu(arr, M)
print(get_answer(mod))

• mod는 분배법칙이 성립
  
  • (a - b) % M = 0
  • (a % M) - (b % M) = 0
  • a % M = b % M
• 구하려는 값
  • (accu[i] - accu[j]) % M = 0
  • i~j 구간의 누적합을 M으로 나눈 나머지가 0
  • 따라서, accu[i] % M = accu[j] % M인 구간
• 조합
  • 각 구간의 mod값의 개수를 저장
    - [1, 2, 3, 1, 2]의 accu는 [1, 3, 6, 7, 9]
    - (mod=0) -> 3개 {3, 6, 9}
    - (mod=1) -> 2개 {1, 7}
  • (mod=0) + 각 mod에서 2개 뽑는 조합 수
    - mod가 같은 값의 쌍 -> accu[i] % M = accu[j] % M
    - 3 + 3C2 + 2C2 = 3 + 3 + 1 = 7

 

다른 사람이 작성한 코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll cnt[1010];
ll arr[1010101];

int main(){
	int n, m; cin >> n >> m;
	for(int i=1; i<=n; i++){
		cin >> arr[i];
		arr[i] += arr[i-1];
		arr[i] %= m;
		cnt[arr[i]]++;
	}

	ll ans = cnt[0];
	for(int i=0; i<m; i++){
		ll now = cnt[i];
		ans += now * (now - 1) / 2;
	}
	cout << ans;
}

• 아래 블로그의 친절한 설명으로 이해
  
  • 코드는 C++

https://justicehui.github.io/ps/2019/04/04/BOJ10986/

백준10986 나머지 합

기억해야할 것

• 문제 접근
  
  • 위 블로그를 보지 않았다면 풀지 못했을 것
  • 수학적으로 접근하는 것도 많이 접해보기