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

연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제이다.

연속된 부분 구간의 합이 M으로 나누어 떨어진다??

문제를 어떻게 해결하여야 하는 거지?? 이 문제를 해결하기 위해서는 아이디어가 필요하다.

 

누적합을 하면서 나머지를 구하는 것이다.

나머지가 1

나머지가 0

나머지가 0

나머지가 1

나머지가 0

 

나머지가 1인 경우를 유심히 관찰해 보자.

1만 있을 때와 1 2 3 1일 때 나머지가 1이다.

이 둘을 빼게 된다면?? 2 3 1이 남는다 2 3 1은 3으로 나누어 떨어진다.

이 아이디어를 이용해서 문제를 해결한다.

 

1. 나머지를 저장하는 배열을 만든다.

2. 배열에는 경우의 수가 저장된다.

3. 배열에 저장된 값을 가지고 2개씩 조합한다.

 

예를 들어 result[1]에 2가 들어 있다. 그러면 나머지가 1인 경우가 2개가 있다는 말이다.

2개를 가지고 조합을 하면?? 2*(2-1)/2 =1이다. 나머지가 1인 경우를 가지고 만들 수 있는 조합이 1개 있다는 의미이다.

result[0]에 3이 들어있다. 그러면 나머지가 0인 경우가 3개가 있다는 말이다.

3개를 가지고 조합을 하면?? 3*2/2=3 이다. 나머지가 0인 경우를 가지고 만들 수 있는 조합이 3개 있다는 의미이다.

 

 

 

자체적으로 나머지가 0이 되는 경우도 3가지가 있다.

 

1+3+3=7