백준 10986

[amm0124]

문제

백준 10986번을 풀었습니다
문제 링크 : https://www.acmicpc.net/problem/10986

설명

길이 N의 수열이 주어지는데, 연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간의 수를 구하는 문제입니다.

접근법

N이 1,000,000까지 주어집니다. n이 작다면, 2차원 배열을 사용해서 쉽게 풀 수 있을텐데 말입니다.
따라서 접근법을 다르게 가야 합니다.
문제에서 핵심은 m으로 나누어 떨어지는 구간의 수를 구하는 것입니다. 아래 두 항목을 통해 접근해봅시다.

1. 구간의 합은 부분합 아이디어를 통해 O(1)만에 해결할 수 있음을 모두 아실 것입니다. 모르시면 공부해보시길 (재미있는 주제입니다. 제가 부분합을 좋아함)
2. (a+b)%m = a%m + b%m입니다.

해설

연속된 구간의 합이 m으로 나누어 떨어진다는 것은 시작점에서 ~ 끝점까지 m으로 나눈 나머지의 합이 0이어야 함을 의미합니다.
만약 어떤 시작점 i의 값 value[i]를 m으로 나눈 나머지를 mod₁이라 해버리면, 조건을 만족하는 끝점 j의 값 value[j]를 m으로 나눈 나머지는 mod₁와 같아야 합니다. 그래야 value[j]%m - value[i]%m == 0이 될 것이니까요.

즉, 배열 내 모든 수에 대해 m으로 나눈 나머지를 구하고, 그 중 2개를 뽑는 경우의 수가 답입니다.

코드

import sys 

n,m = map(int,sys.stdin.readline().split())
seq = list(map(int,sys.stdin.readline().split()))

dp=[0 for _ in range(m)] # 나머지의 수

p=0
for i in range(n):
    p+=seq[i]
    dp[p%m]+=1

ans=dp[0]
for i in range(m) :
    ans += dp[i] * (dp[i]-1) // 2

print(ans)

마무리하며

이번 주는 좀 늦어졌네요 ㅠ.ㅠ 죄송합니다 담주부턴 안늦겠습니닭