[백준] 1977번 완전 제곱수

문제

M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완전제곱수는 64,  81,  100 이렇게 총 3개가 있으므로 그 합은 245가 되고 이 중 최솟값은 64가 된다.

입력

첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10000이하의 자연수이며 M은 N보다 같거나 작다.

출력

M이상 N이하의 자연수 중 완전제곱수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 완전제곱수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

흠 이건.. sqrt를 잘 사용하면 답을 쉽게 맞출 수 있다.

하지만 sqrt만 사용하면 답이 틀린다. 왜냐하면 srqt는 int가 아니기 때문에

즉, 소수이기 때문에 곱하게 되어도 소수이지만

값을 비교 할때는 정수처럼 비교한다. 그래서 틀린답이 나온다.

 

  #include <bits/stdc++.h>
  using namespace std;
  int main () {
    int M,N;
    cin >> M >> N;
    int sum = 0;
    int minN = 10000;
    for(int i = M;i<=N;i++) {
      int temp = floor(sqrt(i));
      if (pow(temp,2) == i) {
        minN = min(minN,i);
        sum += i;
      }
      
    }
    if (minN == 10000 || sum == 0) {
      cout << -1;
    } else {
      cout << minN << "\n" <<sum;
  
    }
  }   

floor가 아닌  (int)로 강제 형변환을 시켜줘도 답을 맞출 수 있다. 이렇게 되면 소수점자리가 전부 날라가고

정수 부분만 남는다. 예를들어 62같은 경우를 보면 sqrt를 해주면 7.XXXXXX이다. 이걸 그냥 제곱 하면 62.XXX가 나오지만 비교할때는 무시하나보다. 그래서 62와 맞는 답이 나온다. 이를 방지하고자

(int)혹은 floor를 사용하면 된다. 이걸 사용하면 이값은 7이 된다.7*7은 49이므로 62와 맞지 않는다.

그래서 답이 아니다.

반대로 64같은 경우는 sqrt를 해면 8, 이걸 제곱하면 64다. 이 두개를 비교하면 다행이 맞다.