[자바] 백준 1977 - 완전제곱수 (java)

 문제 : boj1977

---

 

필요 알고리즘 개념

•  브루트포스
  • 모든 경우를 살펴보는 브루트포스 알고리즘 개념이 필요하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  1<=M<=N<=10000 이다. 그럼 우선 10000 이하의 완전 제곱수가 몇개가 있는지부터 알아야 하는데, 간단히 sqrt(10000) = 100 이므로, 그냥 x=1부터 100까지에 대해 x^2이 이 문제에서 말하는 완전제곱수의 범위이다. 따라서 M,N에 따라 굳이 범위를 나누지 말고 모든 경우를 봐도 O(100)밖에 안된다.

 

  그러니 x=1 ~ x=100에 대해 x^2을 계산해보고 그게 [M, N] 범위 이내라면 결과에 더해주고, 그 중 가장 처음 M을 넘은 x^2을 따로 기록해주면 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        int sum = 0;
        int min = 0;
        for (int i = 1; i <= 100; i++) {
            int pow = i*i;
            if (pow<m || pow>n) continue;
            if (min == 0) min = pow;
            sum += pow;
        }
        System.out.println(min==0?-1:String.format("%d\n%d", sum, min));
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}