[백준 알고리즘] 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

 

내가 작성한 소스 (C++ 성공)

#include <iostream>

using namespace std;

int main(){
    int m, n;
    int dp[10000];
    int sum = 0;
    int mini = 10000;

    cin >> m >> n;

    for(int i=1; i<=n; i++){
        dp[i] = i*i;
    }

    for(int i=1; i<=n; i++){
        if(m <= dp[i] && dp[i] <= n){
            sum += dp[i];
            mini = min(mini, dp[i]);
        }
    }

    if(sum == 0){
        cout << "-1\n";
    } else{
        cout << sum << "\n";
        cout << mini << "\n";
    }

    return 0;
}

 

정리

이 문제는 모든 경우의 수를 한번 계산하고 그 계산한 결과를 가져와 조건에 맞게 사용하면 되기 때문에
동적계획법을 사용해서 쉽게 풀 수 있었다.

배열에 완전제곱수를 1부터 10000 까지 넣어준다.

 for(int i=1; i<=n; i++){
 	dp[i] = i*i;
 }

그리고 문제에서 원하는 값을 완전제곱수를 구해 넣어둔 배열 안에서 조건문으로 찾아 구한다.

 for(int i=1; i<=n; i++){
	if(m <= dp[i] && dp[i] <= n){
		sum += dp[i];
		mini = min(mini, dp[i]);
	}
}

합과 최솟값을 구하는 문제였기 때문에 위의 코드와 같이 작성했다.

그리고 마지막에는 예외처리를 통해 출력해주었다.

if(sum == 0){
	cout << "-1\n";
} else{
	cout << sum << "\n";
	cout << mini << "\n";
}