[백준][C++] 10986: 나머지 합

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

 

10986번: 나머지 합

 

 

 

 

골드 문제로 갈수록 점점 힘들어지는 거 같다.

 

https://cocoon1787.tistory.com/396

 

이 분이 작성한 글을 봐도 봐도 이해가 안되어서 6명 넘는 사람의 글을 찾아서 이해하려고 한 것 같다.

 

많은 글 중에서 이해하고 보니 설명을 제일 잘 한 것 같아서 가져와봤습니다.

---

- 문제

 

 

숫자 배열이 주어지면 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력하는 문제다.

 

 

 

---

- 해설

 

1. 반복문을 통해 0부터 N까지의 누적합을 M으로 나눠서 저장한다.

 

예시) 

1 2 3 1 2

을 보면 M으로 나누지 않은 경우에는 

 

1 3 6 7 9

가 되고, 이걸 M으로 나누면

 

1 0 0 1 0

이 된다.

 

 

 

2. 가장 먼저 if(sum % M == 0) answer++의 경우가 어떤 경우냐면

 

0부터 i까지의 누적합을 M으로 나눈 게 0이 될 때를 말한다.

 

예)

0~2, 0~3, 0~5

(0 ~ 2)3 - 0 = 0
(0 ~ 3)6 - 0 = 0
(0 ~ 5)9 - 0 = 0

 

 

3. 이후 answer += v[i] * (v[i] - 1) / 2의 경우에는  ? ~ ?까지의 합을 말한다.

 

 

1 3 6 7 9

M으로 나누기 전의 누적합을 보면 위와 같다.

 

이걸 보면

6 - 3 = 3

9 - 3 = 6

9 - 6 = 3

7 - 1 = 6

으로 3으로 나누어 떨어지는 경우가 4개가 있다는 것을 알 수 있다. 

 

이걸 M으로 나눈 후에 보면

1 0 0 1 0

(아래 빼기는 index - index로 생각하라)

3 - 2

5 - 2

5 - 3

4 - 1

이렇게 되는 것을 볼 수 있다.

 

0이 3개 있고

1이 2개 있는데,

 

N개, 즉 3개중에서 2개를 고르는 경우는 3 * (3-1) / 2 이고,

N개, 즉 2개 중에서 2개를 고르는 경우는 (2) * (2-1) / 2이다.

 

이건 조합을 구하는 방식인 nCr인 것을 알 수 있따!!!!

 

---

- 풀이

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, temp;
    vector<long long> v(1001, 0);       // int 말고 long long이 필요하다. 범위는 M만큼
    long long sum = 0, answer = 0;      // 이것도 당연히 int형을 초과하므로 long long

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> temp;
        sum += temp;
        v[sum % M]++;                   // 해당 i구간까지의 누적합
        if (sum % M == 0)
        {
            answer++;                   // M으로 나누어 떨어지면 ++
        }
    }
    for (int i = 0; i <= M; i++)
    {
        answer += v[i] * (v[i] - 1) / 2;    // nC2의 느낌으로 풀어야 한다. 설명은 블로그에 !!!
    }

    cout << answer;

    return 0;
}

 

 

---

- 새롭게 알게 된 점