[C++] 백준 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. 반복문으로 M부터 N까지 돌면서

2. 완전제곱수를 구하고

3. 그것들을 더한다, 그리고 그것들을 비교해서 제일 작은수를 출력

이런 순서로 코드를 짰다

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
using namespace std;

int main() {

    int m, n;
    scanf("%d %d", &m, &n);

    int sum = 0;
    int cnt = 0;
    int mini = 10000;
    

    for (int i = m; i <= n; i++) {
        if (sqrt(i) == floor(sqrt(i))) {
            cnt++;
            sum += i;//완전제곱수의 합 
            mini=min(mini, i);
        }
    }
    
    if (cnt == 0) {
        printf("-1");
    }
    else {
        printf("%d\n", sum);
        printf("%d", mini);
    }
    
    return 0;
}

리뷰

먼저 M부터 N까지 반복문을 돌린다

그리고 완전제곱수를 찾아야하는데 sqrt함수를 썼다. 이 함수는 제곱근 함수이다

sqrt(9)는 3이다 제곱근을 계산하는 함수이다

그리고 floor함수를 썼다. 이 함수는 주어진 실수를 가장 가까운 작거나 같은 정수로 내리는 함수이다

sqrt(i) == floor(sqrt(i))

예를 들어 i=8일 때

8의 제곱근은 약 2.828 == 2 가 된다

floor함수를 써서 소수점을 버리면 2가 된다 

 

i=9일 때

9의 제곱근은 3 == 3 이렇게 완전제곱수를 찾는다

floor함수를 써도 애초에 9는 완전제곱수이기 때문에 제곱근에 소수점이 붙지 않기 때문이다

 

그렇게 해서 그것들을 모두 더해준다

그리고 그것들 중에서 가장작은수는 min함수를 썼다

N의 최대범위는 10000라고 했기 때문에 10000와 i를비교해서 가장 작은수를 찾았다

 

마지막으로 빼먹은게 완전제곱수가 없는경우이다 이 경우에는 -1을 출력해야하는데

완전제곱수를 찾을 때마다 cnt를 증가시켰다

cnt가 0이라면 완전제곱수가 없다는 뜻이기 때문에 이 조건을 마지막에 적었다

 

학습

근데 문제의 알고리즘 분류를 보니까 브루트포스 알고리즘이 있다

이 알고리즘은 몰라서 찾아봤다

 

브루트포스 알고리즘은 

그냥 무식하게 모든 경우의 수를 탐색하면서 요구조건에 맞는 결과를 찾는다는 것이다

노가다....???

가장 큰 특징은 모든 영역을 전체 탐색한다

브루트 포스는 크게 두 종류가 있다

선형구조 : 순차 탐색

비선형 구조 : 백트래킹, DFS, BFS

 

1. 주어진 문제를 선형 구조로 구조화한다

2. 답을 찾을 때까지 탐색

3. 답 정리 

근데 이렇게 하니까 가장 큰 단점은

실행 시간이 오래 걸리고 비효율적이다는점..

 

그럼 이 문제를 브루트 포스로 해결한다면

M부터 N까지를 전부 탐색하면 되는건가?

 

 

출처 

1977번: 완전제곱수 (acmicpc.net)

1977번: 완전제곱수