[ 백준 10986] 나머지합 (C++)

 

10986번: 나머지 합

 

 

문제!

---

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

 

---

계속되는 숫자들의 합이 M으로 나누어떨어지는 횟수를 계산하는문제로

누적합을 사용하면 쉽게 풀수있을것 같다는 생각이 드는 문제입니다..

 

 

 

일단 시작!

---

 

바로 1차시도는 실패...

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int N = 0, M = 0;
int answer = 0;
vector<int>list;


int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	int sum = 0;
	int memo = 0;
	
	cin >> N>>M;

	

	list.push_back(0);
	for (int i = 0; i < N; i++) {
		cin >> memo;

		sum += memo;
		list.push_back(sum);
	}

	for (int i = 1; i < N + 1; i++) {
		for (int j = i; j < N + 1; j++) {
			memo = list[j] - list[i - 1];
			if (memo % M==0) {
				answer += 1;
			}
		}
	}


	cout << answer << endl;

	return 0;

}

 

 

일반적인 누적합으로는 시간초과나는 문제네요;;

 

 

여기서 약간의 수학적 사고가 필요했습니다.

 

 

현재 누적합으로 구할수 있는 식은

 

    ( list[j] - list[i] ) %M = 0

 

입니다. 이걸 약간 풀어서 생각해 본다면

 

 list[j] %M = list[i] % M

 

으로 바꿔 볼수있는데

이것은 M으로 나누었을때 나머지가 같은 값끼리 묶어주면?  >> 나머지가 0이되는 누적합을 구할수있는 조합이 나온다?

 

라는 결론을 도출할수있습니다...

그렇다면 이제는 나머지의 갯수가 2이상인 것들을 찾아 

cnt[i] * (cnt[i] - 1) / 2   >> 조합 구하는 식!

 

으로 답을 구해줄수있겠네요

 

신기하네요..

 

 

그렇게 생각 하고 다시 문제를 풀어 보겠습니다.

 

int N = 0, M = 0;
long long answer = 0;


long long cnt[1001] = { 0 };

먼저 변수들을 설정해줍시다.

 cnt >>나머지 갯수를 저장할 배열

 

 

long long sum = 0;
	long long memo = 0;

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> memo;
		sum += memo;
		cnt[sum % M] += 1;
	}

그다음은 입력을 받으면서 cnt[나머지] 의 갯수를 세어줍시다.

 

 

 

그리고 마지막으로 cnt배열을 사용하여 answer+= 조합의수  를 계속해서 최신화 해줍시다.

for (int i = 0; i <= 1000; i++) {
		answer += cnt[i] * (cnt[i] - 1) / 2;
	}


	cout << cnt[0] + answer << endl;

 

 

 

여기까지하면 끝!

(자료형은 long long형으로 사용해줍시다!)

 

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int N = 0, M = 0;
long long answer = 0;


long long cnt[1001] = { 0 };



int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	long long sum = 0;
	long long memo = 0;
	
	cin >> N>>M;

	for (int i = 0; i < N; i++) {
		cin >> memo;
		sum += memo;
		cnt[sum % M] += 1;
	}


	for (int i = 0; i <= 1000; i++) {
		answer += cnt[i] * (cnt[i] - 1)/ 2;
	}


	cout << cnt[0]+answer << endl;

	return 0;

}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!