1977번 - 완전제곱수
이 문제는 브루트 포스로 해결할 경우 result = 0(혹은 ans = 0)으로 설정하여 지정한 범위(M <= x <= N) 안에 선형 탐색(1씩 증가하면서 탐색)하여 완전제곱수이면 더하는 방식으로 해결 가능합니다.
그러나 이 문제는 시그마 공식을 활용하면 브루트 포스 없이 가능합니다.
f(n) = sigma k^2 (from 1 to n) = n * (n + 1) * (2n + 1) / 6
그 다음 해당 공식을 2번 적용하고 두 수의 차를 구하면 바로 정답을 구할 수 있습니다.
예시로 M = 60, N = 100인 경우는 다음과 같이 적용할 수 있습니다.
최소 범위수인 60을 제곱근 취하면 7.xxx가 나오고 올림 처리하면 8 나옵니다.
그 다음 최대 범위수인 100을 제곱근 취하면 10.000이 나오고 내림 처리하면 10 나옵니다.
그 다음 f(10) - f(8-1) 연산을 하여 0이면 -1 출력하고 0 초과인 경우 f(10) - f(8-1) = 385 - 140 = 245, 그리고 최소 완전제곱수는 8^2 = 64가 됩니다.
댓글을 작성하려면 로그인해야 합니다.
kjk9704 1년 전 5
이 문제는 브루트 포스로 해결할 경우 result = 0(혹은 ans = 0)으로 설정하여 지정한 범위(M <= x <= N) 안에 선형 탐색(1씩 증가하면서 탐색)하여 완전제곱수이면 더하는 방식으로 해결 가능합니다.
그러나 이 문제는 시그마 공식을 활용하면 브루트 포스 없이 가능합니다.
f(n) = sigma k^2 (from 1 to n) = n * (n + 1) * (2n + 1) / 6
그 다음 해당 공식을 2번 적용하고 두 수의 차를 구하면 바로 정답을 구할 수 있습니다.
예시로 M = 60, N = 100인 경우는 다음과 같이 적용할 수 있습니다.
최소 범위수인 60을 제곱근 취하면 7.xxx가 나오고 올림 처리하면 8 나옵니다.
그 다음 최대 범위수인 100을 제곱근 취하면 10.000이 나오고 내림 처리하면 10 나옵니다.
그 다음 f(10) - f(8-1) 연산을 하여 0이면 -1 출력하고 0 초과인 경우 f(10) - f(8-1) = 385 - 140 = 245, 그리고 최소 완전제곱수는 8^2 = 64가 됩니다.