백준 1977번: 완전제곱수

 

 

 

---

 

 

문제

M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오.

 

 

실행 결과

 

코드(c++)

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

int main() {
	int a, b;
	cin >> a >> b;
	int sum = 0; int min = -1;
	int n = 1;
	for (int i = a; i <= b; i++) {
		int n = sqrt(i); // 제곱근 함수 사용
		if (n * n == i) {
			sum += i;
			if (min == -1 || min > i) {
				min = i;
			}
		}
	}
	if (sum == 0)
		cout << -1;
	else
		cout << sum << "\n" << min;
	return 0;
}

 

 

 

코드 설명

먼저 완전제곱수의 개념을 알아야 한다.

완전제곱수란 어떤 자연수의 제곱 형태로 표현할 수 있는 수이다.

ex. 1, 4, 9, 16, 25, 36...

 

cmath 라이브러리를 이용해 sqrt 함수를 이용하면 제곱근을 구할 수 있다.

해당 범위 내의 임의의 수의 제곱근을 n이라고 하자.

제곱근 n을 다시 제곱했을 때 원래 i와 같다면 이는 완전제곱수이다.

 

여기서 핵심은 자료형 int 이다.

완전제곱이 아닌 수를 제곱근, 즉 루트화 할 경우 

int 자료형은 소숫점 뒤를 전부 날려버린다..!

 

예를 들어 i가 9일 경우, n은 3으로 정확하게 구해진다.

그러나 만약 i가 10일 경우, 원래 루트 10은 대략 3.1623..이지만 int 형이라 그냥 3이 되어버린다.

따라서 조건식 n * n == i 은 완전제곱일 경우에만 성립한다:)

 

 

 

---

문제 출처: 

1977번: 완전제곱수