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

 문제 : boj6131

---

 

필요 알고리즘 개념

• 브루트포스
  
  • 대상으로 가능한 모든 경우를 직접 보면서 확인해주면 된다.
• 수학
  • 제곱근. 제곱 연산이 필요하다.

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

 

---

 

풀이

  정수 A, B에 대해 1<=B<=A<=500 이고, B^2 + N = A^2 이다.

 

1. B를 1부터 500까지 하나씩 증가시키면서 대입해본다. (브루트포스)

 

2. sqrt(B^2+N)가 500을 초과했다면 1로 되돌아가도 되지만, B를 1부터 500까지 증가시키는 도중이므로 어차피 그 뒤로도 전부 500을 초과할꺼니 거기서 끝내도 동일하다.

 

3. (sqrt(B^2+N))^2 == B^2+N 인지 확인한다. 아니라면 1로 되돌아간다.

이게 뭔지 궁금할 수 있는데, A는 정수여야 한다. 정수인지 확인하는 과정이다. 

 

4. 2,3 모두 통과했다면 카운트 해준다.

 

---

 

코드 : github

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

public class Main {
    private static final int LIMIT = 500;
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;
        for (int i = 1; i <= LIMIT; i++) {
            int cur = i*i+n;
            int sqrt = (int) Math.sqrt(cur);
            if (sqrt > 500) break;
            if (sqrt*sqrt == cur)
                cnt++;
        }
        System.out.println(cnt);
    }

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