[C++백준 1977번:완전제곱수]

문제링크

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

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

 

해석

완전 제곱수를 찾는 방법은 N과 M이 10000이하의 자연수이기 때문에 100 이하 중 제곱해서 만들 수 있는지를 이용하여 알아볼 수 있다.

코드

#include <iostream>
#include <math.h>
using namespace std;
 
int main() {
    int m, n;
    int min;
    int sum = 0;
    cin >> m >> n;
 
    for (int i = n; i >= m; i--) {
        for (int j = 1; j <= 100; j++) {
            if (j == sqrt(i)) {
                min = i;
                sum = sum + i;
            }
        }
    }
    if (sum == 0) {
        cout << -1;
    }
    else {
        cout << sum << '\n';
        cout << min;
    }
}

 

Memo

정확하진 않지만 시간 복잡도를 계산하면서 풀 수 있는 힘을 기른 것 같다.