백준 1977번: 완전제곱수 (C++)

문제

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을 출력한다.

코드

#include <iostream>
#include <cmath>
using namespace std;

int main(void){
    int ins1, ins2;
    cin >> ins1 >> ins2;

    int a = (int)ceil(sqrt(ins1));
    int b = (int)floor(sqrt(ins2));

    if (a > b) {
        cout << "-1" << endl;
    }

    else {

        int min = pow(a, 2);
        int sum = 0;

        for (int i = a; i <= b; i++){
            sum += pow(i, 2);
        }

        cout << sum << endl;
        cout << min << endl;
    }

    return 0;

}

접근 및 풀이

입력 받은 M과 N의 제곱근을 sqrt() 함수로 계산해준 뒤 완전제곱수를 만들 수 있는 자연수의 범위를 구한다. 이 과정에서 M의 제곱근은 ceil() 함수를 이용하여 올림해주고, N의 제곱근은 flood() 함수를 이용하여 버림해준다.

올림과 버림을 사용하는 이유는 예를 들어 설명해보겠다. M = 60, N = 105라고 했을 때 M의 제곱근은 7.xx일 것이고, N의 제곱근은 10.xx일 것이다. 이러한 상황일 때 완전제곱수를 만들 수 있는 수는 7.xx보다 큰 8부터 10.xx보다 작은 10일 것이다. 설령 M과 N이 완전제곱수이더라도 올림과 버림을 사용한다면 정확한 범위를 구할 수 있다.

구한 제곱근을 a와 b로 두고 최솟값과 합을 구한다

만약 M과 N 사이에 완전제곱수가 없다면 제곱근의 소숫점 자리를 뗀 자연수는 같아진다. 이 상태에서 a와 b에 각각 올림과 버림을 적용한다면 a가 b보다 큰 값을 갖게 되기 때문에 이를 통해 완전제곱수가 있는지의 여부를 판단해 주고, -1을 출력한다.

풀면서 얻은 교훈...

난 나름 효율적인 로직이라 생각했는데 자꾸 틀렸다고 해서 로직이 틀린 줄 알았는데 알고 보니 중간에 변수에 초기화를 안해줘서 자꾸 틀렸다고 한 거였다… 로컬에서 돌릴 땐 IDE가 자동으로 초기화를 해줘서 깜빡해버렸다 제일 기본을 까먹은 내가 너무 한심했다 변수를 쓸 땐 꼭 초기화 해주자