새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 10986 나머지 합

by 언호 2022. 6. 22.

📖 문제


🧑🏻‍💻 풀이 과정

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번: 나머지 합

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)

www.acmicpc.net

 

 

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

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 2211 네트워크 복구  (0) 2022.06.24
[백준] 2616 소형기관차  (0) 2022.06.23
[백준] 3584 가장 가까운 공통 조상  (0) 2022.06.21
[백준] 2580 스도쿠  (0) 2022.06.20
[백준] 1937 욕심쟁이 판다  (0) 2022.06.17

댓글