[BAEKJOON] No.10986 Python

daye_ 2023. 1. 25. 15:07

나머지 합

10986번: 나머지 합

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

www.acmicpc.net

처음으로 짠 코드.

순서쌍만을 생각해서 하나씩 접근했다.

import sys

N,M = map(int,input().split())
N_list = list(map(int,input().split()))

print(N_list)

rst = 0

for i in range(N) :
  for j in range(i,N) :
    print("\n[",i,",",j,"]")
    sum=0
    for k in range (i,j+1) :
      print("N_list[",k,"] = ",N_list[k])
      sum += N_list[k]
    print("sum = ",sum)
    if (sum!=0)and(sum%M==0) : 
        print("**** find num ****\n")
        sum = 0
        rst+=1

     
pprint("\n결과 : ",rst)

5
3
1 2 3 1 2
[1, 2, 3, 1, 2]

[ 0 , 0 ]
N_list[ 0 ] =  1
sum =  1

[ 0 , 1 ]
N_list[ 0 ] =  1
N_list[ 1 ] =  2
sum =  3
**** find num ****


[ 0 , 2 ]
N_list[ 0 ] =  1
N_list[ 1 ] =  2
N_list[ 2 ] =  3
sum =  6
**** find num ****


[ 0 , 3 ]
N_list[ 0 ] =  1
N_list[ 1 ] =  2
N_list[ 2 ] =  3
N_list[ 3 ] =  1
sum =  7

[ 0 , 4 ]
N_list[ 0 ] =  1
N_list[ 1 ] =  2
N_list[ 2 ] =  3
N_list[ 3 ] =  1
N_list[ 4 ] =  2
sum =  9
**** find num ****


[ 1 , 1 ]
N_list[ 1 ] =  2
sum =  2

[ 1 , 2 ]
N_list[ 1 ] =  2
N_list[ 2 ] =  3
sum =  5

[ 1 , 3 ]
N_list[ 1 ] =  2
N_list[ 2 ] =  3
N_list[ 3 ] =  1
sum =  6
**** find num ****


[ 1 , 4 ]
N_list[ 1 ] =  2
N_list[ 2 ] =  3
N_list[ 3 ] =  1
N_list[ 4 ] =  2
sum =  8

[ 2 , 2 ]
N_list[ 2 ] =  3
sum =  3
**** find num ****


[ 2 , 3 ]
N_list[ 2 ] =  3
N_list[ 3 ] =  1
sum =  4

[ 2 , 4 ]
N_list[ 2 ] =  3
N_list[ 3 ] =  1
N_list[ 4 ] =  2
sum =  6
**** find num ****


[ 3 , 3 ]
N_list[ 3 ] =  1
sum =  1

[ 3 , 4 ]
N_list[ 3 ] =  1
N_list[ 4 ] =  2
sum =  3
**** find num ****


[ 4 , 4 ]
N_list[ 4 ] =  2
sum =  2

결과 :  7

답은 잘 나오지만 시간초과.

https://smhope.tistory.com/380

144. 10986(나머지 합) - 파이썬

import sys input = sys.stdin.readline N,M= map(int, input().split()) num = list(map(int, input().split())) sum = 0 numRemainder = [0] * M for i in range(N): sum += num[i] numRemainder[sum % M] += 1 result = numRemainder[0] for i in numRemainder: result +=

smhope.tistory.com

참고자료

import sys
input = sys.stdin.readline

N,M= map(int, input().split())
num = list(map(int, input().split()))
sum = 0
numRemainder = [0] * M

for i in range(N):
  sum += num[i]
  numRemainder[sum % M] += 1

result = numRemainder[0]

for i in numRemainder:
  result += i*(i-1)//2
  
print(result)

파이썬으로 첫 문제 풀어봐서 좀 헷갈린다.