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

 

---

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

예제 입력 1 

60
100

예제 출력 1 

245
64

예제 입력 2 

75
80

예제 출력 2 

-1

---

N과 M의 값 제한이 최대 10000이라 그냥 단순 무식하게 1부터 100까지 모든 수들을 제곱시키고 배열에 넣어서 N과 M 사이에 값들이 배열에 존재하는 값인지 확인하는 형식으로 구현했습니다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n, m, cnt = 0;
    cin >> n >> m;
    vector <int> v;
    for (int i = 1; i <= 100; i++) {
        int x = i * i;
        v.push_back(x);
    }
    int ck = 0, sma = 0;
    for (int i = n; i <= m; i++) {
        if (binary_search(v.begin(), v.end(), i)) {
            cnt += i;
            if (ck == 0) {
                sma = i;
                ck = 1;
            }
        }
    }
    if (cnt == 0) {
        cout << -1; 
        return 0;
    }
    cout << cnt << '\n' << sma;
}