[BOJ] 1699. 제곱수의 합

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

풀이방법 : DP + 약간의 생각

​

1트 : 실패 Why? TLE

1. DP[n] = k, n을 만드는데 필요한 최소 숫자의 개수 라고 table 정의

​

DP[1] = 1

DP[2] =2 // 1 + 1

DP[3] = 3 // 1 + 1 + 1

DP[4] = 1 // 2^2

​

이런식으로 해서

DP[10]을 구할땐, DP[1]+DP[9], DP[2]+DP[8] .. DP[5]+DP[5]

이렇게 하면 최솟값을 찾을 수 있겠다고 생각했다.

​

뇌 없이 코딩을 하고 제출을 했는데 TLE였다. 보니까 N이 10만 이었다. O(N^2)은 불가능했다.

#include<bits/stdc++.h>
using namespace std;
int DP[100005];
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    int range;
    
    
    cin >> n;
    range = (int)sqrt(n);
    fill(DP,DP+n+1, 2e+9);
    for(int i = 1; i <= range; i++)
    {
        DP[i*i] = 1;
    }   
    DP[2] = 2;

    for(int i = 3; i <= n; i++)
    {
        for(int j = 1; j <= i/2; j++)
        {
            DP[i] = min(DP[i], DP[i-j] + DP[j]);
        }
    }
    cout << DP[n];

    
    return 0;
}

틀렸다.

​

O(sqrt(n)N)도 힘들어보였다 . 한 10^7.5 니까..

근데 무식하게 다 보는게 아니고, 약간의 생각을 곁들인...

​

C^2 = a^2 + b^2 이런식으로 표현하는데, 최대한 적은 a,b,c를 쓰려면 숫자들이 큼직큼직 해야한다.

숫자들이 크면서 제곱수이면 best이다.

​

또한 DP[4], DP[9] 이런것들은 제곱수라서 무조건 1이다.

또한 DP[8], DP[18]같은것들은 *2를 한 것들은 무조건 최소가 2이다.

이런식으로 2까지는 미리 구해줬다.

​

그 이후에는 제곱수끼리만 더해보게 했다.

ex) 19의 경우

(1,4,9,16)이 가능하다.

DP[1] + DP[18]

Dp[4] + DP[15]

DP[9] + DP[7]

Dp[16] + Dp[2] 여기서 최소를 구하면 된다.

​

그랬더니 안전하게 통과가 됐다.

 

#include<bits/stdc++.h>
using namespace std;
int DP[100005];
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    int range;
    int t;
    
    cin >> n;
    range = (int)sqrt(n);
    fill(DP,DP+n+1, 2e+9);
    for(int i = 1; i <= range; i++)
    {
        DP[i*i] = 1;
        if(i*i*2 <= n)
        {                
            DP[i*i*2] = 2;   
        }
    }
    for(int i = 3; i <= n; i++)
    {
        if(DP[i] == 1 || DP[i] == 2) continue;
        range = (int)sqrt(i);
        for(int j = 1; j <= range; j++)
        {
            DP[i] = min(DP[i], DP[i-j*j] + DP[j*j] );
        }   
    }
    cout << DP[n];

    
    return 0;
}

 

end