[백준 1977번] 완전제곱수 - C++ 풀이

https://www.acmicpc.net/problem/1977
(백준 문제 링크)

1. 문제 설명

문제

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

2. 풀이

이 문제는 단순하게(Naive) 구현하는 방식으로 해결 가능합니다.

M이상 N이하 구간 내의 수 A가 1부터 100까지의 수의 제곱과 같은지 검사하는 방식으로 해결합니다.

예를 들어 $M=2$, $N=7$이면 구간 내의 수 A는 2, 3, 4, 5, 6, 7이 될 수 있습니다. 각각의 수가 1부터 100까지의 제곱수 1, $2^2$, $3^2$, ..., $100^2$와 동일한지 검사합니다. 이 방식은 비효율적일 수 있지만 문제를 해결하는데에는 전혀 문제 없습니다.

1부터 100까지의 수만 검사하는 이유는 주어지는 수는 최대 10000이며, 이는 $100^2$이기 때문입니다.

구간에 포함되는 수의 최대 개수는 10000이며, 각 수에 대해 100개의 수와 비교하여 검사하므로, $100 \times 10000$번만큼의 연산을 하게되며, 이는 주어진 시간 제한내에 해결 가능합니다.

3. 정답 코드

#include<iostream>
using namespace std;

int main() {
    long long int M, N, sum=0, min;
    cin >> M >> N;
    for(long long int i=N; i>=M; i--) {
        for(long long int j=1; j<=100; j++) {
            if(j*j == i) {
                sum += i;
                min = i;
                break;
            }
        }
    }
    if(sum) {
        cout << sum << endl;
        cout << min;
    }
    else {
        cout << -1;
    }
    return 0;
}