[Python/파이썬] 백준 3673번 나눌 수 있는 부분 수열

3673번: 나눌 수 있는 부분 수열

 

문제

양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오.

예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누어 떨어지는 것의 개수는 6개이다.

2, 1, 2, 1, 1, 2, 1, 2

다음과 같은 부분 수열은 합이 4로 나누어 떨어진다. 1~8, 2~4, 2~7, 3~5, 4~6, 5~7번째

입력

첫째 줄에 테스트 케이스의 개수 c가 주어진다. (1 ≤ c ≤ 200) 각 테스트 케이스는 두 줄로 이루어져 있다.

테스트 케이스의 첫째 줄에는 d(1 ≤ d ≤ 1,000,000)와 수열의 크기 n(1 ≤ n ≤ 50,000)이 주어진다. 다음 줄에는 수열의 원소가 주어진다. 각 숫자는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 정수이다.

출력

각 테스트 케이스에 대해서, 주어진 수열의 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 출력한다.

코드

for _ in range(int(input())):
    d, n = map(int, input().split())
    arr = list(map(int, input().split()))

    mod = [0]*d
    sum = 0
    ans = 0
    for a in arr:
        sum = (a+sum) % d   # (sum+현재 수 a)를 d로 나눴을 때의 나머지
        # d로 나머지가 같은 애들끼리 뺄셈을 하면 d의 배수가 됨
        ans += mod[sum]
        mod[sum] += 1
    ans += mod[0]
    print(ans)

 

d로 나눴을 때 나머지가 같은 수끼리 빼면 d의 배수가 된다.

그러므로 현재 수 이전에 같은 나머지를 가졌던 수들과는 모두 합이 d의 배수인 부분 수열을 만들 수 있다는 말이다. 그렇기 때문에 수열의 각 수마다 본인 이전까지의 수열에서 나머지가 같은 수의 개수인 mod[sum]을 ans에 더해주고, 본인도 mod[sum]에 더해주어야 하니까 mod[sum]의 값을 1 증가시켜준다.