백준 3673 <나눌 수 있는 부분 수열> Python

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

---

우선 리스트를 부분합 리스트로 치환해줍니다. 연산 시 걸리는 시간을 줄이기 위함입니다.

그 뒤에 'd 로 나누어 떨어진다' 의 부분을 쉽게 풀어 볼 생각을 해야합니다.

조건에서 데이터의 크기는 최대 50000 개인데 해당 데이터를 2중 반복문으로 순회하면 시간 초과가 발생하기 때문입니다.

 

결론적으로, 어떠한 두 수 A, B의 차가 d 로 나누어 떨어지려면 A 를 d 로 나눈 나머지와 B 를 d 로 나눈 나머지가 같으면 됩니다.

 

A = ad + q, B = bd + p 라고 가정하겠습니다.

A - B = d(a-b) + (q - p) 입니다.

A - B 가 d 로 나누어 떨어지려면 모든 인수가 d 로 나누어떨어지면 됩니다.

d(a-b) 는 이미 d 의 배수이므로 나누어 떨어지고 남은 수는 (q-p) 인데 0<=q, p<d 이므로 -d<q-p<d 입니다.

-d<k<d 의 범위에서 d 의 배수인 k 는 0 뿐이므로 q-p = 0 이어야 합니다.

즉, A 와 B 를 d 로 나눈 나머지가 같으면 됩니다.

 

우리는 d 로 나눈 나머지가 궁금하므로 부분합 리스트를 미리 d 로 나누어 나머지만 보기로 하겠습니다.

하지만 리스트를 순회하며 같은 나머지를 찾으면 어차피 2중 반복문임은 똑같기 때문에 다른 방법을 찾아야 합니다.

 

같은 나머지를 가진 수가 k 개라면 해당 수(인덱스) 들의 조합의 수는 kC2 = k(k-1)/2 입니다.

즉 리스트에서 같은 나머지를 가진 위치의 수만 검색하면 단순한 계산으로 수를 알 수 있게됩니다.

---

import sys

from collections import Counter

input = sys.stdin.readline

def solution(d, n, data_list):

    # 결과

    result = 0

    # 누적합 리스트

    subsum = [0] + data_list[:]

    for i in range(1, n+1):

        subsum[i] += subsum[i-1]

        # 미리 나누기

        subsum[i] %= d

    # 같은 나머지를 가진 수 카운터

    subsum_counter = Counter(subsum)

    # 같은 나머지를 가진 수 끼리 빼면 d 로 나누어떨어짐

    # 큰 수에서 작은수를 빼야 하므로

    # 빼서 d 로 나누어떨어지는 수의 쌍은

    # (k)(k-1)/2 , k 는 해당 나머지를 가진 수의 개수

    for key, value in subsum_counter.items():

        # 한 개 뿐이면 세지 않음

        result += value*(value-1)//2

    return result

# 입력

c = int(input().strip())

for _ in range(c):

    d, n = map(int, input().strip().split())

    data_list = list(map(int, input().strip().split()))

    print(solution(d, n, data_list))