BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/10986
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
내가 작성한 코드
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
- 각 구간의 mod값의 개수를 저장
다른 사람이 작성한 코드
#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 나머지 합
문제 링크 http://icpc.me/10986
justicehui.github.io
기억해야할 것
- 문제 접근
- 위 블로그를 보지 않았다면 풀지 못했을 것
- 수학적으로 접근하는 것도 많이 접해보기
'코딩테스트' 카테고리의 다른 글
[백준][재귀] 종이의 개수 (0) | 2022.03.24 |
---|---|
[백준][세그먼트트리] 최솟값과 최댓값 (0) | 2022.03.23 |
[프로그래머스] 다리를 지나는 트럭 (0) | 2022.03.12 |
[코딩테스트] 프로그래머스 카카오 코딩테스트 기출 복기3 (0) | 2022.03.12 |
[코딩테스트] 프로그래머스 카카오 코딩테스트 기출 복기2 (0) | 2022.03.10 |