728x90
풀이
단순히 가장 큰 제곱수로 수를 구성하는 방법은 최소 제곱수의 개수의 만족이 성립하지 않는다.
때문에, 입력받은 n까지 모든 수에 대해 계산을 해봐야 한다.
Square Free Integer같은 경우 이전의 수를 구성하는 제곱수의 개수 + 1을 만족하며
이러한 수의 밀집도는 리만 가설이 참이라는 전제하에 약 61%이다.
("백준 1557, 제곱 ㄴㄴ" 중 "Mobius function의 반환값의 개수 추측")
따라서 다음과 규칙을 기본으로 사용했다.
for (int i = 1; i <= n; i++){
dp[i] = dp[i-1] + 1;
n >= 4 일 때는 Square Free Integer가 아닌 수들도 존재하며, 처음에 언급했듯이 가장 큰 제곱수의 구성이 최소 제곱수의 개수를 만족하지 않으므로, 구성 가능한 제곱수들 중 최소 제곱수의 개수를 찾아야 한다.
for (int j = 2; j*j <= i; j++)
dp[i] = min(dp[i], dp[i-j*j] + 1);
소스코드
#include <stdio.h>
#define min(a, b) a > b ? b : a
int dp[50001];
int main(){
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++){
dp[i] = dp[i-1] + 1;
for (int j = 2; j*j <= i; j++)
dp[i] = min(dp[i], dp[i-j*j] + 1);
}
printf("%d", dp[n]);
}
출처 및 참고자료
17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
[백준 1557] 제곱 ㄴㄴ [C]
풀이 Mobius function와 Mertens function로 풀이했다. 편의상 "제곱ㄴㄴ수"는 SFI(Square Free Integer, 제곱 인수가 없는 정수)라고 부르겠다. Mobius function Mobius function은 다음의 조건에 따라 값을 반..
kyr-db.tistory.com
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 4355] 서로소 [C] (0) | 2021.08.11 |
---|---|
[백준 11689] GCD(n, k) = 1 [C] (0) | 2021.08.11 |
[백준 15657] N과 M (8) [C] (0) | 2021.08.10 |
[백준 15654] N과 M (5) [C] (0) | 2021.08.10 |
[백준 15652] N과 M (4) [C] (0) | 2021.08.10 |