[Python] 백준 10986번 나머지 합

나머지가 같은 수를 고른다면, 그 둘 사이의 값은 나머지가 0이 된다는 게 메인 포인트같다.

 

예를 들어.. 1 2 3 1 2 의 숫자가 주어진다면, 구간합은 1 3 6 7 9가 된다.

1 3 6 7 9 를 3으로 나눈 값은 1 0 0 1 0 이 된다.

만약 구간을 A[0] ~ A[3] 으로 정했다면, 7(1,2,3,1) - 1 = 6이 되고, 나머지는 0이 된다.

 

# 나머지가 같은 경우 중 2개를 뽑는 경우의 수 계산 에서 if문 범위를 > 1 로 한 이유는

범위로 뽑는 수는 시작과 끝 2개인데, 나머지가 같은 수가 2개 이상 존재해야 2개를 뽑을 수 있기 때문이다.

# 나머지 합
# N개의 수가 주어진다. 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
# 즉 A(j) + ... + A(i) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
# 첫째 줄에 N, M이 주어진다. 둘째 줄에 N개의 수가 주어진다.
# 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

# 수 입력
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
origin = list(map(int, input().split()))
cnt = 0

# 구간합 생성
sum = [0]
for i in range(n):
    sum.append(sum[i] + origin[i])

# 구간합 수정 (M으로 나눈 나머지)
for i in range(n + 1):
    sum[i] %= m

# 나머지 별로 개수 세어진 배열 생성
remain = [0 for i in range(m)]
for i in range(1, n + 1):
    z = sum[i] % m
    if z == 0:  # 나머지가 0이라면 정답 += 1
        cnt += 1
    remain[z] += 1

# 나머지가 같은 경우 중 2개를 뽑는 경우의 수 계산
for i in range(m):
    if remain[i] > 1:
        cnt += remain[i] * (remain[i] - 1) // 2

print(cnt)

구간합 만들 때 범위 생각을 잘못해서 삽질 좀 했다.. ㅎㅎ

주의하라고 했던 부분에서 그대로 실수를.. 앞으로는 구간 설정에 좀 더 주의해야 겠다.

https://ksha0628.tistory.com/161

[알고리즘] 구간 합

 

다른 풀이를 찾아보니 구간합 배열 sum을 따로 만들지 않고 origin에서 바로 변환하던데 이 문제에선 그렇게 해도 괜찮을 것 같다.

문제에 따라서 유동적으로 하거나.. 한 방법만 확실히 익히거나 해야할 듯