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

입력값 1<= m <= n <= 10,000 가 주어졌을 때 m이상 n이하의 완전제곱수들의 합과 그중 최소값을 출력하는 문제이다.

 

특히 이렇게 입력 범위가 작을 때 제곱과 관련된 문제는 입력값이 주어진 후에 일일히 루트값을 연산하는 것 보다, 

처음부터 1부터 시작해서 제곱수를 넣는 것이 더 안전하다.

10,000의 루트값은 100이라서 오히려 1부터 시작하면 최대 100번의 제곱 연산을 하면 되는데,

만약 입력 범위가 9,000부터 10,000이라고만 해도 1,000번이나 연산을 해야한다.

 

따라서 나는 다음과 같이 코드를 짰다.

 

1. 벡터를 만들어서

2. 1부터 100까지 자연수에 대해 완전제곱수를 push 한다.

이때 계산한 제곱수가 m보다 작으면 push하지 않고

n보다 크면 push 하지 않고 break한다.

3. 범위 내의 제곱수가 없으면 -1을 출력한다

4. 조건에 맞는 제곱수가 하나라도 있으면 for문을 돌아 합을 구하고 출력한다

5. 벡터의 0번 index에 있는 값이 최소값이므로 출력한다.

 

 

정답 코드

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

int m, n;
vector<int> v;

int main(){
    cin >> m >> n;
    for(int i = 1 ; i <= 100; i++ ){
        int squareNumber = i * i;
        if(squareNumber < m) continue;
        if(squareNumber > n) break;
        v.push_back(squareNumber);
    }

    if(v.size() == 0){
        cout <<"-1\n";
        return 0;
    }

    int sum = 0;
    for(int squareNumber : v){
        sum += squareNumber;
    }

    cout << sum <<"\n" << v[0];
    return 0;
}

 

문제 링크 : https://www.acmicpc.net/problem/1977