1699번

1699번 - 제곱수의 합

1.완전탐색 코드 - 시간 초과

2. DP 코드 - 시간초과

3. DP 코드 - 정답코드

D[N] = N을 제곱수의 합으로 나타낼 때, 최소갯수.

처음엔 완전 탐색을 통해서 풀었고, 역시나 시간 초과가 났다.

그리고 두번째로 DP 를 통해서 풀었는데 오류가 두가지가 생겼다. 그 두가지 모두 for 문 상에서의 코딩방식에 의해 생겼다.

1. 불필요한 범위를 계산함에 따라 int형 정수의 범위를 초과하는 수가 생기는 것을 인지하지 못했다.

2. 첫번째 문제점을 인지하고 고쳤으나, 불필요한 범위 때문에 시간초과가 발생하였다.

<두번째 DP 코드 - 시간 초과>

go() 함수에서의 for문에서 문제가 발생하였음.

처음에는 i * i 의 값이 만약 n 값이 100000일 경우 int 값을 벗어나는 것을 보고 오류 고쳤다 ! 하고 좋아했지만

이 코드는 결국 시간초과를 발생시켰다.

나는 i를 n부터 1까지 모두 불필요하게 체크했기 때문이다. 반절이 넘는 값이 헛돌고 있었다.

그래서 정답코드에서 고쳤다.

#include<iostream>
#include<algorithm>
using namespace std;
 
int N;
int D[100001];
 
int go(int n)
{
    if (n == 0)
    {
        return 0;
    }
 
    if (D[n] != n)
    {
        return D[n];
    }
 
    for (long long i = n; i >= 1; i--)
    {
        if (n - (i*i) >= 0)
        {
            D[n] = min(D[n], go(n - (i*i)) + 1);
        }
    }
 
    return D[n];
}
int main()
{
    cin >> N;
 
    for (int i = 0; i<100001; i++)
    {
        D[i] = i;
    }
    cout << go(N) << endl;
 
    return 0;
}

<정답 코드 DP>

i의 값을 딱 지정된 범위까지만 돌게해주었다.

사실 위의 오답 코드에서는 제곱값을 큰 수 부터 체크해서 D값을 빨리 찾아야겠다는 생각으로 저렇게 짰는데..

결국 캐시값을 빨리 찾는것은 중요하지 않았다. 어차피 완전탐색이기 때문에 전부다 찾아서 캐시값이랑 비교하기 때문이었다..

정답 코드로 짜다보니 if문도 제거할 수 있었다.

#include<iostream>
#include<algorithm>
using namespace std;
 
int N;
int D[100001];
 
int go(int n)
{
    if (n == 0)
    {
        return 0;
    }
 
    if (D[n] != n)
    {
        return D[n];
    }
 
    for (long long i = 1; i*i<=n ; i++)
    {
            D[n] = min(D[n], go(n - (i*i)) + 1);
    }
 
    return D[n];
}
int main()
{
    cin >> N;
 
    for (int i = 0; i<100001; i++)
    {
        D[i] = i;
    }
    cout << go(N) << endl;
 
    return 0;
}