[백준] 10986 나머지 합

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

특정 구간의 합이 특정 수로 나누어 떨어지는 경우를 찾아야했습니다.

구간의 합을 빠르게 구하기 위하여 누적합을 이용하였습니다.

숫자만큼 반복하여 처음부터 마지막 수까지 누적합을 구하였고, 특정 수로 나눈 나머지만을 구하여 기록하였습니다.

 

 구간의 시작과 마지막이 동일한 경우는 나머지가 0으로 기록되면 경우의 수에 포함할 수 있으므로 누적합에서 0으로 기록된 개수를 찾으면 됬으므로 간단하였습니다.

그러나 모든 구간들의 나머지를 구하기 위해 2중 반복문을 사용하였으나 입력으로 무수히 많은 수가 들어온다면 시간초과 문제가 발생하였습니다.

2중 반복문을 사용하지 않고, 경우의 수를 구하는 방법이 필요했습니다.

 

누적합의 A~B 구간의 합의 나머지가 X 이고, A~C 구간의 합의 나머지도 X 라면, (B+1)~C 구간 합은 나누어 떨어지게 됩니다.

이러한 방식으로 경우의 수를 쉽게 구할 수 있습니다.

그리하여 같은 나머지 값들의 개수를 갖고 2개를 선택하여 경우의 수를 구할 수 있었습니다.

2) 알고리즘

• 누적합

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N, M = map(int, sys.stdin.readline().split())                           # 숫자의 개수, 나눌 수
nums = list(map(lambda x: int(x) % M, sys.stdin.readline().split()))    # 입력 숫자들을 M으로 나눈 나머지들
acc_nums = [0]                                                          # 누적합 초기 0 추가
cnt = [0] * M                                                           # 각 나머지들 개수 기록할 리스트
answer = 0

for i in range(N):
    num = (acc_nums[-1] + nums[i]) % M          # i+1 까지의 누적 합(M으로 나눈 나머지만 기록) 
    acc_nums.append(num)                        
    cnt[num] += 1                               # 나머지 개수 추가
    if not num:                                 # 나머지가 0인 경우에는 i == j 인 경우에 나누어 떨어짐
        answer += 1

for num in cnt:                                 # 나머지의 개수를 이용해 구간별 경우의 수 구하기
    answer += num * (num-1) // 2

print(answer)

---

🔗 문제 링크

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

10986번: 나머지 합

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다