출처 : https://www.acmicpc.net/problem/10986
참고 : https://banwolcode.tistory.com/47
문제
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
입력값 : (1 <= n <= 10^6, 2 <= M <= 10^3) , (0 <= A <= 10^9)
생각
- 2차원 배열로 하나씩 확인하는게 방법인가?
- 일단 누적합인데
- n 번째에서 n-1번까지 확인해야 하기 때문에 이건 너무 n(n-1)/2 번인데 -> 이건 시간초과날꺼 같고
- 그렇다고 크기가 1인 것에서 n인거 까지 하나씩 늘려서 확인하는것도 같은 복잡도..
- 순서가 보장 되어 있는것도 아니고..
- 뭐 일단은 나머지에대한 것들로 해볼까..
- 아무리 생각해도 현재 내 능력치로 풀 수 없는 문제 -> 인터넷 검색
코드
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<ll> nums(n+1, 0);
vector<int> remainders(m, 0);
for(int ix = 1; ix <= n; ++ix)
{
int num;
cin >> num;
nums[ix] = (nums[ix-1] + num);
++remainders[nums[ix] % m];
}
// 일단 바로 나누어 떨어지는것
ll count = remainders[0];
// 나머지가 같은 것끼리 조합해서 푸는 방식
for(int ix = 0; ix < m; ++ix)
{
// 없는 갯수에 대한 것은 기본으로 0 * -1 이 되기 때문에 고민할 필요가 없음
// 최소한 2개는 골라야 하기 때문에 1개인 것도 1 * 0 이 되어서 걸러짐
count += remainders[ix] * (remainders[ix] - 1) / 2;
}
cout << count;
}
틀린 이유
vector<int> remainders(m, 0);
- 이 부분 최대 입력값이 10^6 인데 뭐가 문제인지 모르겠음
수정 코드
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<ll> nums(n+1, 0);
vector<ll> remainders(m, 0);
for(int ix = 1; ix <= n; ++ix)
{
int num;
cin >> num;
nums[ix] = (nums[ix-1] + num);
++remainders[nums[ix] % m];
}
// 일단 바로 나누어 떨어지는것
ll count = remainders[0];
// 나머지가 같은 것끼리 조합해서 푸는 방식
for(int ix = 0; ix < m; ++ix)
{
// 없는 갯수에 대한 것은 기본으로 0 * -1 이 되기 때문에 고민할 필요가 없음
// 최소한 2개는 골라야 하기 때문에 1개인 것도 1 * 0 이 되어서 걸러짐
count += remainders[ix] * (remainders[ix] - 1) / 2;
}
cout << count;
}
결과
- 문제 풀이 시간 : 못 품
- 메모리 : 9836 KB
- 시간 : 152 ms
배운점 및 고칠점
- 1시간 고민 했지만 나오지 않았음
- 이런 누적합 문제에 대해 알게 됨
- 아직도 이해가 안되는 int가 안됨 -> 이건 형변환에 대해 문제가 있던거.