[자바] 백준 23128 - Math (java)

목차

문제 : boj23128

 

 

필요 알고리즘

• 수학, 브루트 포스 (brute force)
  
  • 약간의 수학적 직관으로 범위를 좁히면, 그냥 브루트 포스로 다 대입해보면 답을 구할 수 있다.

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

 

 

풀이

  문제에서 제시된 찾고자 하는 내용을 수식으로 나타내보면 다음과 같이 나타낼 수 있다. A와 B는 각각 a_i와 a_j를 뜻한다. C는 임의의 정수이다.

 

  여기서 A, B의 범위는 [1, 1000000] 이다. 따라서 임의의 C를 구하더라도, C^2 - A^2 은 양수여야 하고, 가능한 최대값은 100만이다. 이 경우 최악의 경우인 A가 1인 경우에도 C^2의 최대치는 100만-1 이면 되므로, 어차피 대충 1000번정도만 살펴보면 됨을 알 수 있다. 즉, 기존 수식을 살짝 바꿔 한쪽을 제곱이 아닌 녀석으로 교체하면서 범위를 제한하는 아이디어가 필요한 문제였다.

 

  즉, B가 존재하는지를 O(1)로 알 수 있도록 Set 같은걸 사용하고 + 모든 배열의 원소 A에 대해 살펴보는데 최대 100만개이다. O(1000000)  + C^2-A^2을 최대 100만까지만 살펴보면 되는데, 이게 최악의 경우에 1000번이므로 O(1000) 이다. 따라서 O(1 * 1000000 * 1000)에 해결 가능하다.

int cnt = 0;
for (long cur : arr) {	// A를 정한다.
    long num = cur+1;	// C^2-A^2이 양수여야 하므로 A+1부터 살펴보면 된다.
    long tmp;
    while ((tmp = num*num - cur*cur) <= 1000000) {	// C^2-A^2은 100만까지만 보면 된다
        if (set.contains(tmp)) {	// 그러한 B가 존재하면 카운팅해준다.
            cnt++;
        }
        num++;	// C를 증가시켜서 계속 살펴본다.
    }
}
System.out.println(cnt);

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

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

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        Set<Long> set = new HashSet<>();
        long[] arr = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            set.add(arr[i] = Long.parseLong(st.nextToken()));
        }

        int cnt = 0;
        for (long cur : arr) {
            long num = cur+1;
            long tmp;
            while ((tmp = num*num - cur*cur) <= 1000000) {
                if (set.contains(tmp)) {
                    cnt++;
                }
                num++;
            }
        }
        System.out.println(cnt);
    }
}