배수들의 합

17173번: 배수들의 합

 

나의 풀이

import sys

def _basu_sum(N, M, basu_list):
    answer = 0
    for n_num in range(1, N+1):
        for i in basu_list:
            if (n_num % i) == 0:
                answer += n_num
                break
    return answer   

N, M = map(int, sys.stdin.readline().rstrip().split())
basu_list = list(map(int, sys.stdin.readline().rstrip().split()))
print(_basu_sum(N, M, basu_list))

 

시간 복잡도

for n_num in range(1, N+1) : N 이하의 수를 1 부터 순회 ( 선형 시간 복잡도 )
	for i in basu_list : 배수 조건에 맞으면 증감 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n**2) )