[BAEKJOON]NO.1977完全平方数

4776 ワード
baekjoon C テキストリンク

今日は1977回の完全平方数を解きました
解けて3ヶ月前にすでに解けたことを発見して、ほほほ
でもこの時はゴムとちょっと違うみたい
完全二乗数とは、整数の積で表すことができる数です.
ex.整数がnの場合、nxnの数(64、81、100、...)を作成できます.
1.3ヶ月前の解答(C)
#include <stdio.h>

int main(void)
{
    int m = 0, n = 0;
    scanf("%d", &m);
    scanf("%d", &n);

    int i, j;
    int isPresence = 0;
    int arr[n-m];

    int idx = 0;
    int sum = 0;
    for(i=m; i<=n; i++)
    {
        // 완전 제곱 수 찾기
        for(j=1; (j*j)<=i; j++)
        {
            if(j*j==i)
            {
                arr[idx++] = i;
                isPresence = 1;
            }
        }
    }

    int min = arr[0];
    for(i=0; i<idx; i++)
    {
        sum += arr[i];
        if(arr[i] < min)
        {
            min = arr[i];
        }
    }

    if(isPresence)
        printf("%d\n%d\n", sum, min);
    else
        printf("-1\n");
    
    return 0;
}
2.今日解いた(C++)
#include <iostream>
using namespace std;

int main(void)
{
    int m = 0, n = 0;

    cin>>m;
    cin>>n;

    int size = 100;
    int perfect_square_numbers[100];

    int startIdx = 0; // 탐색 시작 인덱스 구하기
    bool isGetStartIdx = false;
    for(int i=1; i<= size; i++)
    {
        perfect_square_numbers[i-1] = (i*i);
        // 만약 완전제곱수의 값이 m보다 크면 그 전 수가 startIdx가 됨 
        if(!isGetStartIdx)
        {
            if (perfect_square_numbers[i - 1] > m)
            {
                startIdx = i - 2;
                isGetStartIdx = true;
            }
        }
        
    }

    int total = 0;
    bool isFindMin = false;
    int min = 0;
    for(int i=m; i<=n; i++)
    {
        for(int j=startIdx; j<size; j++)
        {
            if(i == perfect_square_numbers[j])
            {
                if(!isFindMin)
                {
                    min = i;
                    isFindMin = true;
                }
                total += i;
            }
        }

    }

    if(total == 0 && min == 0)
    {
        cout<<-1<<endl;
    }
    else
    {
        cout<<total<<endl;
        cout<<min<<endl;
    }
    
    return 0;
}
3.今日解いた改良版?
  • 最初に配列をすべて100番インデックスに埋め込むのは効率的ではないようです.
    endIdxも決まりました
  • それから変数が多すぎて、上に整理しました.
    • #include <iostream>
using namespace std;

int main(void)
{
    int m = 0, n = 0;
    int min = 0;
    int total = 0;
    int size = 100;
    int startIdx = 0; // 탐색 시작 인덱스 구하기
    int endIdx = 0;
    
    bool isGetStartIdx = false;
    bool isGetEndIdx = false;
    bool isFindMin = false;
    bool isFindPerfect = false;

    int perfect_square_numbers[100];

    cin>>m;
    cin>>n;

    for(int i=1; i<= size; i++)
    {
        perfect_square_numbers[i-1] = (i*i);
        // 만약 완전제곱수의 값이 m보다 크면 그 전 수가 startIdx가 됨 
        if(!isGetStartIdx)
        {
            if (perfect_square_numbers[i - 1] > m)
            {
                startIdx = i-2;
                isGetStartIdx = true;
            }
        }
        else if(!isGetEndIdx)
        {
            if(perfect_square_numbers[i-1] >= n)
            {
                endIdx = i-1;            
                isGetEndIdx = true;
                break;
            }
        }
    }
    
    // 완전제곱수 찾기
    for(int i=m; i<=n; i++)
    {
        for(int j=startIdx; j<=endIdx; j++)
        {
            if(i == perfect_square_numbers[j])
            {
                isFindPerfect = true;
                if(!isFindMin)
                {
                    min = i;
                    isFindMin = true;
                }
                total += i;
            }
        }
    }

    if(!isFindPerfect)
    {
        cout<<-1<<endl;
    }
    else
    {
        cout<<total<<endl;
        cout<<min<<endl;
    }
    
    return 0;
}
    3ヶ月前に解いた問題がもっと簡単で効率的だったのは何ですか.のように思われる
    ユニティが来たからユニティで解いたみたい
    この問題は満足するより残念だ
    配列を書き込むのは、入力値の最大値が10000であるためです.
    では、100人分の並びを作るだけでいいと思いますが、簡単そうに見えます.
    完全な平方数の配列を事前に作成した場合.
    次に範囲の値と配列の値を比較し、総数と最小値を求めます.
    計算量と時間はmからnまでの計算より短くなると思います.
    以降の改良バージョンでも.
    startIdxまたはendIdxを制限することで、計算量が減少します.
    今度は並べ替えを書かないようにしてみます.
    プログラマ-ハザード数
    Array.prototype.sort()