[BOJ] 백준 1977 완전제곱수

출처: https://www.acmicpc.net/problem/1977

Approach

완전탐색 기법이란? 유형 문제이다.

완전탐색 기법이란?

 

두 수 N, M이 10000 이하의 자연수이기 때문에

M, N 사이의 특정 구간을 모두 탐색해도 TLE가 발생하지 않는다.

for문으로 탐색하되, 완전 제곱수를 i * i로 표현

- M과 N사이의 숫자인지

- 해당 되는 완전 제곱수들의 합

- 최소값 처리

---

#include <iostream>

const int MAX_NM = 1e4;
inline int min(int A, int B) { return A < B ? A : B;}

using namespace std;

int ansSum, ansMin = MAX_NM + 5;
int M, N, square;

int main() 
{
	// freopen("input.txt", "r", stdin);
	cin >> M >> N;
	
	for (int i = 1; i <= MAX_NM; ++i)
	{
		square = i * i;
		// 완전 제곱수가 M보다 큰 경우
		if (square >= M)
		{
			if (square > N)
				break;

			// M <= 완전 제곱수 <= N 인 경우
			ansSum += square;
			ansMin = min(ansMin, square);
		}
	}

	if (ansSum == 0)
	{
		cout << -1 << endl;
	}	
	else 
	{
		cout << ansSum << endl;
		cout << ansMin << endl;
	}
}

 

Java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int M = Integer.parseInt(sc.next());
		int N = Integer.parseInt(sc.next());
		
		int cnt = 0;
		
		int reM = (int)Math.ceil(Math.sqrt(M));
		int reN = (int)Math.floor(Math.sqrt(N));
		
		// 완전 제곱수의 합산
		int sum = 0;
		for(int i=reM; i<=reN; i++) {
			cnt++;
			sum += i*i;
		}
		
		if(cnt == 0) {
			System.out.println(-1);
		}else {
			System.out.println(sum);
			System.out.println(reM * reM);
		}
	}
}