[C] 백준 1977번 문제

가장 처음에는 M과 N이 10000이하이므로 for문으로 1부터 100까지 돌려서 범위에 해당하면 더하는 방식으로 하려고 했으나 역시나 시간초과로 실패했다!

 

두번째로 생각한 방법은,

완전제곱수가 아닌 수의 제곱근은 완전한 정수가 아닐테니 그걸 다시 제곱하면 다른 값이 나오지 않을까..? 했는데 같은 값이 나와서 실패

 

세번째로 생각한 방법은,

 

제곱근에 10을 곱하고 int 변수에 저장한 뒤 다시 10을 나눈 나머지 값을 확인해서 0 이면 완전제곱수로 판단하는 방법이다. 두번째방법과 비슷한 논리로 완전제곱수가 아닌 수의 제곱근은 정수가 아닌 실수인 점을 이용했다.

ex) 63의 제곱근 = 7.9372539 에 10을 곱하면 79.XXX이고 이를 int 변수에 저장하면 79 이므로 여기서 10을 나눈 나머지는 0이 아닌 9이다.

64의 제곱근인 8에 10을 곱하면 80이고 여기서 10을 나눈 나머지는 0이므로 완전제곱수로 판단을 하는 것이다.

 

근데 여기서 문제점은 int 변수에 저장하는 과정에서 소수점에서 올림이 되는건지 완전제곱수가 아닌 경우에도 나머지가 0이 나오는 경우가 생겼다. 이 이유는 따로 공부를 해봐야할 것 같다.

 

문제점은 10 대신 1000을 곱하고 1000을 나눈 나머지를 구하는걸로 바꾸니까 해결됐다! 정확도가 더 높아져서 그런듯

 

#include <stdio.h>
#include <math.h>

int main()
{
    int a,b,c = 0,sum=0;
    int check;
    scanf("%d",&a);
    scanf("%d",&b);
    
    for (int i = b; i >= a; i--)
    {
        check = (double) sqrt(i) * 1000;
        if(check % 1000 == 0)
        {
            sum += i;
            c = i;
        }
    }
    
    if(sum == 0)
        printf("-1");
    else
        printf("%d\n%d\n",sum,c);
    return 0;
}