주어진 정수 X가 있다고 가정하고 처음 N개의 자연수의 합이 값 X를 초과하지 않도록 최대값 N을 찾아야 합니다.
따라서 입력이 X =7과 같으면 2가 N의 가능한 최대 값이므로 출력은 2가 됩니다. N =3의 경우 계열의 합은 X =7을 초과하므로 1^2 + 2^ 2 + 3^2 =1 + 4 + 9 =14.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
sum_of_squares() 함수를 정의합니다. N
이 걸립니다. -
해상도 :=(N *(N + 1) *(2 * N + 1)) / 6
-
반환 해상도
-
기본 방법에서 다음을 수행하십시오 -
-
낮음 :=1
-
높음 :=100000
-
N :=0
-
낮음 -=높음 동안 수행
-
중간 :=(높음 + 낮음) / 2
-
sum_of_squares(mid) −=X이면
-
N :=중간
-
낮음 :=중간 + 1
-
-
그렇지 않으면
-
높음 :=중간 - 1
-
-
-
반환 N
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def sum_of_squares(N):res =(N * (N + 1) * (2 * N + 1)) // 6 return resdef get_max(X):low, high =1, 100000 N =0 동안 low <=high:mid =(high + low) // 2 if sum_of_squares(mid) <=X:N =mid low =mid + 1 else:high =mid - 1 return NX =7print(get_max(X))입력
7출력
2