{프로젝트 오일러/Project Euler} 1. N보다 작은 3과 5의 배수의 합

한국어/Hackerrank - 한국어 버전과 문제가 다를 수 있습니다. 채점은 Hackerrank를 추천합니다.

N개의 양의 정수가 주어질때 각 숫자보다 작은 3과 5의 배수의 합을 출력하는 문제

(조건: 입력받는 수의 개수 N, 입력받은 수 M)

def get_sum_of_mutiples(num, target):
	amt = num//target
	return target*amt*(amt+1)//2
for _ in range(int(input())):
	m = int(input())
	total = get_sum_of_mutiples(m-1, 3) + get_sum_of_mutiples(m-1, 5) - get_sum_of_mutiples(m-1, 15)
	print(total)

# amt_threes, amt_fives, amt_fifteens = (m-1)//3, (m-1)//5, (m-1)//15
# total = (3*amt_threes*(amt_threes+1) + 5*amt_fives*(amt_fives+1) - 15*amt_fifteens*(amt_fifteens+1))//2​

 

이 문제는 단순하게 풀자면 이중 반복문을 통해 N번 반복하며 1부터 M까지 돌며 3과 5의 배수들을 일일히 더할 수도 있다.

그러나 이 방식은 O(N*M)의 복잡도를 가지게 되며 Hackerrank의 입력 범위를 보면 최악의 경우 10^14번 돌아야 한다는 것을 알 수 있다.

하지만 이 문제는 O(N)으로 풀 수 있는데 바로 위의 코드가 그 방법이다.

문제를 살짝 바꿔서 3과 5의 배수의 개수를 찾는 문제라고 가정해봅시다.

그러면 간단히 (M-1)//3+(M-1)//5-(M-1)//15으로 구할 수 있습니다. (M-1인 이유는 M은 포함하지 않기 때문입니다.)

여기서 (M-1)//3을 T라고 두면 3의 배수의 합은 3*1+3*2+3*3+....+3*T이고 이는 3*(1+2+3+...+T)가 됩니다.

수학적으로 1부터 N까지의 값은 N*(N+1)/2로 구할 수 있습니다.

그러므로 위 식은 3*T*(T+1)/2가 되고 T와 T+1중 하나는 짝수이므로 3*T*(T+1)//2로 3의 배수의 합을 구할 수 있습니다.

이를 통해 5의 배수의 합은 5*T*(T+1)//2, 15의 배수의 합은 15*T*(T+1)//2로 구할 수 있습니다.(여기서 T는 M보다 작은 특정 수의 배수)

위의 코드는 M보다 작은 어떤 수의 배수의 합을 함수화한 것이며 코드 밑의 주석은 함수를 없앤 코드이다.