c언어 10986번 나머지 합 (백준)

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

10986번: 나머지 합

#include <stdio.h>
#include <stdlib.h>

#define l long long

int main(void)
{
	unsigned l int ans = 0; //답
	l int n, m;
	scanf("%lld%lld", &n, &m); //몇 개?, 무엇으로 나눔?
	
    //n개 입력받으므로, (index 시작을 1로 잡았다) n+2개만 있으면 된다고 생각했으나, 2칸을 더 늘려줌
    //n+2로 했을 때는 틀렸음
	l int *a = (l int*) malloc(sizeof(l int) * (n+3)); //동적 할당
	l int *sum = (l int*) malloc(sizeof(l int) * (n+3)); // 동적 할당
	a[0] = 0; //index을 1부터 하기에, a[0]은 0으로 두었다.
	sum[0] = 0;
	
	for(l int i = 1; i<=n; i++) //수 입력 받기
	{
		a[i] = 0;
		sum[i] = 0;
		static l int tmp = 0;
		scanf("%lld", &tmp);
		a[i] = a[i-1] + tmp; //부분합 
	}
	
	for(l int i = 0; i<=n; i++) //부분합들을 m으로 나눈 나머지들이 종류(?)별로 몇 개인지를 계산
	{
		static l int tmp = 0;
		tmp = a[i] % m;
		sum[tmp]++;
	}
	
	for(l int i = 0; i<m; i++)
	{
		l int tmp = 0;
		//개수가 0또는 1이면  0이다.
		if(sum[i] == 0 || sum[i] == 1) tmp = 0;
		else if(sum[i] == 2) tmp = 1; //2개 있는 경우 순서쌍은 1개만 존재한다.
		else {
			tmp = sum[i] * (sum[i]-1); //3개 이상은, nC2 을 따른다.
			tmp /= 2;
		}
		ans += tmp; //구한 값을 ans에 누적시킨다.
	}

	printf("%lld", ans); //출력
	free(a); //풀어줌
	free(sum); //풀어줌
	return 0;
}

 

풀이 :

5 3

1 2 3 1 2

 

0) 부분합과 부분합 % m을 담을 배열을 동적 할당한다. 이때 넉넉하게 만들어 놓는 것이 좋다.

여담 : n개 입력 받을 경우, (index을 난 1부터 시작했으므로) n+1만 있으면 된다고 생각했으나, 계속 틀렸습니다가 나와서, 넉넉하게 n+3으로 주었더니 통과했다.

 

1) 부분합을 구한다.

단 a[0] = 0으로 두고 시작한다.

부분합 : 0 1 3 6 7 9

 

2) 부분합들 % m을 한다

부분합 % m : 0 1 0 0 1 0

 

3) 부분합 % m을 보면 알 수 있듯이 같은 나머지를 가진 부분합들은 큰 것에서 작은 것을 빼서 나온 값은 m에 나누어 떨어진다.

ex) 

        부분합 : 0 1 3 6 7 9

부분합 % m : 0 1 0 0 1 0  

            7 - 1 = 6이며, 6은 3에 나누어 떨어진다.

        부분합 : 0 1 3 6 7 9

부분합 % m : 0 1 0 0 1 0  

            9 - 6 = 3 이며, 3은 3에 나누어 떨어진다.

...

 

4) 즉 나머지가 같은 것들을 2개씩 묶은 개수들을 구하면 된다.

부분합 % m : 0 1 0 0 1 0

나머지_0 : 4개     이 중 2개씩을 고르는 것이므로, 4C2이다.

나머지_1 : 2개     이 중 1개씩을 고르는 것이므로, 2C2 = 1이다.

 

만약 특정한 나머지가 0 또는 1개밖에 없다면, 짝을 못 만들기 때문에 만들 수 있는 개수는 0이다.

 

같은 나머지의 개수 : 0, 1 : 0개

같은 나머지의 개수 : 2     : 1개

같은 나머지의 개수 : n>2 : nC2 개

 

내 생각 : c언어에선 정수형 끼리의 나눗셈은, 소수점 부분이 버림 되기에 나누기를 할 때는, 먼저 곱하고 난 뒤, 나누는 것이 좋다고 나는 생각한다.