[1977번] 완전 제곱수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. bitset STL

int형 배열은 1억개의 배열을 형성 할 수 없다. 왜냐하면 4byte이기 때문에 1억개의 배열을 생성 시 오류가 발생하게 된다.

하지만 bitset는 결국 bitset하나당 1byte이기에(1 or 0을 가진다.) 10000*10000의 제곱수 상황에 대해 해결 할 수 있게 된다.

    for (int i = 1; i <= 10000; i++)

        a[i*i] = true;

이부분에서 1~10000의 제곱수에 대한 값을 모두 a bitset에 저장하게 되는것이다.

예를들어 10000*10000의 제곱수는 a[100000000] = 1로 저장이 될 것이다.

물론 이 내용을 bitset이 아닌 bool 배열로 해결해도 답을 얻을 수 있게된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <iostream> #include <bitset>   using namespace std;   bitset<100000001> a;   int main() {     int n, m, min = -1, sum = 0;       a.reset();       for (int i = 1; i <= 10000; i++)         a[i*i] = true;       scanf("%d %d", &n, &m);       for (int i = n; i <= m; i++)         a[i] == true ? sum += i : 0;       for (int i = n; i <= m; i++)     {         if (a[i] == true)         {             min = i;             break;         }     }       min == -1 ? printf("-1\n") : printf("%d\n%d\n", sum, min);     return 0; } //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus