[백준 17626] Four Squares [C]

백준 - 17626

---

풀이

단순히 가장 큰 제곱수로 수를 구성하는 방법은 최소 제곱수의 개수의 만족이 성립하지 않는다.

때문에, 입력받은 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

[백준 1557] 제곱 ㄴㄴ [C]