[백준] 10986번 나머지 합 (파이썬)

dongEon·2024년 4월 25일
0

문제링크: https://www.acmicpc.net/problem/10986

문제해결 아이디어

  • 1차원 배열의 누적합 문제이다
  • 누적합의 나머지가 같은 수 끼리 빼면 나머지가 0이 된다
  • 예제의 누적합의 경우 [1, 3, 6, 7, 9] 인데 나머지가 1인 1과 7을 빼도 나머지가 0이 된다.
  • 나머지값 별로 개수를 배열에 저장하고 조합을 통해서 정답을 구한다.

소스코드

import sys

input = sys.stdin.readline

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

nums =  list(map(int, input().split()))

prefix_sum = [0] * n

prefix_sum[0] = nums[0]

for i in range(1,n):
    prefix_sum[i] = prefix_sum[i-1] + nums[i]

mod = [0] * m # 나머지 배열

for i in prefix_sum:
    mod[i%m] += 1 # 나머지가 같은 수의 개수를 구함

answer = mod[0] 

for i in mod:
    answer += i*(i-1) // 2 #조합을 통해 개수를 추가 ex)iC2

print(answer)
profile
개발 중에 마주한 문제와 해결 과정, 새롭게 배운 지식, 그리고 알고리즘 문제 해결에 대한 다양한 인사이트를 공유하는 기술 블로그입니다

0개의 댓글

관련 채용 정보