【LeetCode】279.전체 제곱(Perfect Squares) 동적 계획/4제곱 및 정리
제목 설명
정수 n을 정하고 완전한 제곱수 몇 개를 찾아라. (예: 1, 4, 9, 16,...) 그것들의 합은 n과 같다.너는 완전한 제곱수의 개수를 최소화해야 한다.
예 1:
입력: n = 12 출력: 3 설명: 12 = 4 + 4 + 4.
예 2:
입력: n = 13 출력: 2 해석: 13 = 4 + 9.
해결 방법
방법1: 동적 기획
dp[i]에 i의 최소 완전 제곱수를 저장합니다.n, dp[n]=1+dp[n-t2]에 대해 t2는 n보다 크지 않은 완전 제곱수이고 조건을 충족시키는 t를 두루 돌아다니며 최소값은 dp[n]이다.
구현 코드:
class Solution
{
public:
int numSquares(int n)
{
vector<int> dp(n + 1);
int top = 1;
for (int i = 1; i <= n; i++)
{
if (i == (top + 1) * (top + 1))
top++;
dp[i] = 1 + dp[i - top * top];
for (int j = top - 1; j >= 1; j--)
dp[i] = min(dp[i], 1 + dp[i - j * j]);
}
return dp[n];
}
};
방법2:4제곱과 정리
Lagrange 4제곱과 정리: 모든 정수는 4개의 정수의 제곱과 정리를 나타낼 수 있다.중요한 추론: 4제곱과 정리의 수 n을 만족시키고 n=4a(8b+7)를 반드시 만족시킨다.
결과는'1, 2, 3, 4'네 가지만 가능하다는 것을 알 수 있다.다음 상황을 순서대로 판단한다. (1)ans=4, 추론에 만족하는지 판단한다.(이 과정에서 4의 배수로 n을 축소하면 최종 결과에 영향을 주지 않는다)(2)ans=1로 축소된 n이 제곱수인지 판단한다.(3)ans=2, 축소된 n이 두 제곱수로 구성될 수 있는지 판단한다.(4)ans = 3, 이상으로 만족하지 않으면 결과는 3.
구현 코드:
static const auto ioSyncOff = []()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();
class Solution
{
public:
int numSquares(int n)
{
while (n % 4 == 0)
n /= 4;
if (n % 8 == 7)
return 4;
if (isSquare(n))
return 1;
for (int i = sqrt(n); i >= 1; i--)
{
if (isSquare(n - i * i))
return 2;
}
return 3;
}
inline bool isSquare(int n)
{
int t = sqrt(n);
return t * t == n;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
