우리에게 숫자 N이 주어졌습니다. 목표는 정육면체의 합이 N이 되도록 정렬된 양수의 쌍을 찾는 것입니다.
순진한 접근 방식
1부터 N까지의 모든 숫자를 탐색하고 완전제곱수인지 확인합니다. 만약 floor(sqrt(i))==ceil(sqrt(i)).
그러면 그 수는 완전제곱수입니다.
효율적인 접근
N 미만의 완전제곱수는 다음 공식을 사용하여 찾을 수 있습니다. floor(sqrt(N)).
예를 들어 이해합시다.
입력
N=20
출력
Count of square numbers: 4 Count of non-square numbers: 16
설명
Square numbers are 1, 4, 9 and 16. Rest all are non-squares and less than 20.
입력
N=40
출력
Count of square numbers: 6 Count of non-square numbers: 34
설명
Square numbers are 1, 4, 9, 16, 25, 36. Rest all are non-squares and less than 40.
순진한 접근 방식
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
-
정수 N을 취합니다.
-
함수 squareNums(int n)는 n을 취하고 완전제곱 또는 비제곱인 n 미만의 수를 반환합니다.
-
초기 변수 개수를 0으로 간주합니다.
-
for 루프를 사용하여 i=1에서 i<=n
까지 순회 -
floor(sqrt(i))==ceil(sqrt(i))인 경우 숫자는 완전제곱이므로 카운트를 증가시킵니다.
-
모든 루프의 끝에서 개수는 완전제곱에 해당하는 총 개수를 갖게 됩니다.
-
N-제곱은 제곱이 아닌 숫자입니다.
예시
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int squareNums(int n){
int count = 0;
for (int i = 1; i <= n; i++){
if(floor(sqrt(i))==ceil(sqrt(i)))
{ count++; }
}
return count;
}
int main(){
int N = 40;
int squares=squareNums(N);
cout <<endl<<"Count of squares numbers: "<<squares;
cout <<endl<<"Count of non-squares numbers: "<<N-squares;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of squares numbers: 6 Count of non-squares numbers: 34
효율적인 접근
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
-
정수 N을 취합니다.
-
가변 제곱 =floor(sqrt(N))을 취합니다.
-
가변 제곱은 N 아래에 여러 개의 완전 제곱을 갖습니다.
-
N-제곱은 N 미만의 비제곱 수가 됩니다.
예
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
int N = 40;
int squares=floor(sqrt(N));
cout <<endl<<"Count of squares numbers: "<<squares;
cout <<endl<<"Count of non-squares numbers: "<<N-squares;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of squares numbers: 6 Count of non-squares numbers: 34