[백준/Python] 10986 나머지 합

[백준/Python] 10986 나머지 합

정답 코드 및 설명

전체 코드

n, m = map(int, input().split())
a = list(map(int, input().split()))

# 누적 합 배열 계산
s = [0] * (n+1)
for i in range(1, n+1):
    s[i] = s[i-1] + a[i-1]

# 나머지에 대한 카운트 배열
remainder_count = [0] * m
for sum_value in s:
    remainder_count[sum_value % m] += 1

# 조건을 만족하는 구간의 개수 계산
result = 0
for count in remainder_count:
    if count > 1:
        result += count * (count - 1) // 2

print(result)

문제 설명

주어진 숫자 리스트에서 연속된 숫자들의 합이 특정 숫자 M 으로 나누어 떨어지는 구간(부분 리스트)의 개수를 찾는 것이다.

예를 들어 리스트가 [1,2,3,1,2] 이고 M = 3 일 때 이 리스트에서 합이 3으로 나누어 떨어지는 연속된 구간을 찾아야 한다.

• [1,2] 의 합이 3 M = 3 으로 나누어 떨어진다
• [2,1]
• [1,2,3]
• [3]
• [2,3,1]
• [3,1,2]
• [1,2,3,1,2]

총 7개 구간이 조건을 만족한다.

문제 접근 방법

1. 누적 합 계산 : 먼저 리스트의 각 위치까지의 합을 순서대로 계산한다.
2. 나머지 활용 : 누적 합의 각 값에 대해 M 으로 나눈 나머지를 계산한다. 같은 나머지를 가지는 누적 합의 값들 사이에는 그 차이가 M 의 배수라는 것을 의미하므로 이 구간의 합은 M 으로 나누어 떨어진다.
3. 구간 개수 계산 : 나머지가 같은 누적 합의 값들이 몇 번 나타났는 지 수를 센다. 나머지가 0 인 경우 합 자체가 M 으로 나누어 떨어지는 경우를 의미하므로, 이 경우도 포함된다.
4. 결과를 출력한다.

코드 설명

1. n 과 m 을 입력 받고 a 리스트 각 요소를 입력받는다.
2. 누적합 배열 계산

• n+1 크기의 리스트 s 를 생성하고 모든 요소를 0으로 초기화한다. s 는 누적합을 저장할 배열이다.
• for 루프 를 사용하여 리스트 a의 각 요소에 대해 누적 합을 계산하고, s 에 저장한다. s[i]는 a 리스트의 첫 번째 요소부터 i 번째 요소까지의 합을 나타낸다.

3. 나머지에 대한 카운트 배열

• 길이가 m 인 리스트 remainder_count 를 생성하고, 모든 요소를 0 으로 초기화 한다. 이 배열은 누적 합의 나머지 값을 카운트한다.
• 누적 합 배열 s를 순회하며 각 요소를 m 으로 나눈 나머지를 계산한다. 계산된 나머지를 인덱스로 사용하여 remainder_count 배열의 해당 요소를 1 증가시킨다.

4. 조건을 만족하는 구간의 개수를 계산한다

• result 결과를 저장할 변수 를 0으로 초기화한다.
• remainder_count 배열을 순회하며, 각 나머지 값이 나타난 횟수 count 에 대해 조건을 만족하는 구간의 개수를 계산한다. 구간의 개수 count 가 2 이상일 때, count * ( count - 1 ) /2 로 계산한다. 이는 해당 나머지를 가지는 누적 합의 값들 사이에서 2개를 선택하는 조합의 수를 의미한다.
• 각 나머지 값에 대해 계산된 구간의 개수를 result 에 더한다

5. 결과를 출력한다.