[백준] 10986 : 나머지 합 (파이썬)

누적합, 수학 문제

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

---

접근 방식

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

부분구간의 개수를 구해야 하므로 투포인터 알고리즘을 잠깐 떠올렸으나 주어진 데이터의 앞뒤 연관성이 없기 때문에 다른 방법을 고안해냈다.

 

투포인터 알고리즘을 쓸 수 없는 이유

1) 투포인터 알고리즘의 일반적인 사용 사례

투포인터 알고리즘은 주로 다음과 같은 조건을 만족하는 경우에 사용된다.

1. 정렬된 배열: 배열이 정렬된 상태에서 특정 합을 찾는 문제.
2. 특정 조건을 만족하는 구간: 예를 들어, 구간의 길이 또는 합이 특정 조건을 만족하는 경우.
3. 단일 스캔: 한 번의 배열 스캔으로 문제를 해결할 수 있는 경우.

2) 투포인터 알고리즘의 예시

다음은 투포인터 알고리즘을 사용할 수 있는 전형적인 문제 예시이다.

• 배열에서 두 수의 합이 특정 값이 되는 경우 찾기
• 구간의 합이 특정 값을 넘지 않도록 하는 최대 길이의 구간 찾기

이러한 문제들은 주로 배열의 요소 간의 관계가 정렬되어 있거나, 구간의 시작과 끝을 조정하면서 조건을 만족할 수 있는 문제이다.

 

3) 이 문제에서 투포인터를 사용할 수 없는 이유

하지만 이 문제에서는 다음과 같은 이유로 투포인터 알고리즘이 적합하지 않다.

1. 부분합의 조건:
   • 문제의 요구사항은 구간의 합이 M으로 나누어 떨어지는 경우이다. 이는 단순히 구간의 합이 특정 값을 넘지 않거나, 특정 값을 이루는 문제와는 다르다.
   • 부분합이 M으로 나누어 떨어진다는 조건을 만족하기 위해서는 각 구간의 합을 정확히 계산하고, 이를 M으로 나눈 나머지를 이용해 조건을 만족하는 구간을 찾아야 한다.

---

문제의 핵심

이 문제는 누적합과 나머지를 활용한다.

• 누적 합(prefix sum)을 사용하여 각 위치까지의 합을 계산하고, 이를 M으로 나눈 나머지를 별도의 배열에 저장한다.
• 동일한 나머지를 가지는 누적합을 활용한다.
  핵심은 나머지가 같은 두개의 구간을 고른 후 두 구간을 빼주어 해당 구간이 M으로 나누어 떨어지게 만들어주는 것이다.

---

💡 풀이 코드 (성공)

import sys 
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

def sol(n, m, arr):
    remainder = [0] * (m)

    sum = 0
    for i in range(n):
        sum += arr[i]
        remainder[sum % m] += 1

    ans = remainder[0]
    for i in remainder:
        ans += i * (i - 1) // 2
    
    print(ans)

sol(n, m, arr)

 

주요 로직

1. 나머지 배열 생성

0 ~ (m - 1) 사이의 나머지가 몇 번 나타나는지를 기록하는 remainder 배열을 생성한다.

remainder = [0] * (m)

 

2. 누적합 구간의 나머지 구하기

누적합을 계산하고, 해당 구간까지의 누적합을 m으로 나눈 나머지를 remainder 배열에 카운트한다.

remainder[sum % m]은 현재 누적 합을 m으로 나눈 나머지를 의미한다.

sum = 0
for i in range(n):
    sum += arr[i]
    remainder[sum % m] += 1

 

3. M으로 나누어 떨어지는 구간의 개수 구하기

나머지가 이미 0인 구간들의 갯수를 ans의 초깃값으로 지정해준다.

나머지가 이미 0인 구간들은 아래와 같이 "동일한 나머지를 가진 두 누적합 구간을 선택한 후 빼서 나머지를 0으로 만드는 작업"을 하지 않아도 이미 조건을 만족하기 때문이다.

ans = remainder[0]

---

 

동일한 나머지를 가진 두 누적 합 구간을 선택한 후 빼주면, 두 구간의 차이는 나머지가 0이 되므로 M으로 나누어 떨어진다.

따라서, 동일한 나머지를 가지는 누적 합 구간 내에서 2개를 선택하고(nC2), 이를 ans에 더해준다.

for i in remainder:
    ans += i * (i - 1) // 2

---

참고문헌

https://smhope.tistory.com/380

144. 10986(나머지 합) - 파이썬

 

https://code-angie.tistory.com/26

[백준 BOJ / Python] 10986번 나머지 합 (누적합)