[자바] 백준 7588 - Amicable (java)

목차

문제 : boj7588

 

 

필요 알고리즘

• 수학, 정수론
  
  • 약수 구하는 것과 관련된 정수론 문제이다.

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

 

 

풀이

  N이 최대 백만이고, 테스트케이스가 존재한다. 따라서 미리 백만까지의 모든 Amicable 쌍을 구해둔 후, 각 테스트케이스마다 알맞게 출력해주면 된다.

 

  여기서 구현이 필요한 부분은 결국 어떠한 수가 주어졌을 때, 그 수의 모든 제수의 합을 구하는 녀석이 필요하다. 이 때, 주어진 수의 제곱근까지만 확인해보면 되는데 그 이유는 '에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유' 글을 참고해보면 알 수 있다.

public int sumOfDivisors(int n) {
    int limit = (int) Math.sqrt(n);
    int sum = 1;
    for (int i = 2; i <= limit; i++) {
        if (n%i==0) sum += i + (n/i);
    }
    if (limit * limit == n) sum-=limit;
    return sum;
}

 

 

  Amicable 쌍을 미리 구성해두는 방법은, 그냥 100만 이하의 모든 수를 확인하면서 찾아보면 된다. 시간복잡도로 보면 O(100만*sqrt(100만)) 이라 오래걸릴 것 같지만, set으로 쳐낸 것도 있고해서 생각보다 그렇게 오래걸리지 않는다.

private List<int[]> initAmicablePairs() {
    List<int[]> amicablePair = new ArrayList<>();
    Set<Integer> alreadyChecked = new HashSet<>();

    for (int i = 2; i <= LIMIT_OF_INPUT; i++) {
        if (alreadyChecked.contains(i)) continue;

        int a = sumOfDivisors(i);
        if (i >= a || a > LIMIT_OF_INPUT) continue;

        if (sumOfDivisors(a) == i) {
            amicablePair.add(new int[]{i, a});
            alreadyChecked.add(a);
        }
    }
    return amicablePair;
}

 

 

  또, 사실 100만 이하에서 이렇게 찾을 수 있는 쌍이 40개도 안되기 때문에 그냥 미리 저거 돌린 후에 코드에 40개도 안되는 쌍을 미리 넣어두면 빠르게 동작하는 코드를 짤 수도 있다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

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

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

    public void solution() throws Exception {
        List<int[]> amicablePair = initAmicablePairs();

        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;

            sb.append('\n').append("Amicable numbers between 1 and ").append(n).append('\n');
            int cnt = 0;
            for (int[] cur : amicablePair) {
                if (cur[1] <= n) {
                    sb.append(cur[0]).append(' ').append(cur[1]).append('\n');
                    cnt++;
                }
            }
            if (cnt == 0) {
                sb.append("None\n");
            }

        }

        System.out.print(sb);
    }

    private List<int[]> initAmicablePairs() {
        List<int[]> amicablePair = new ArrayList<>();
        Set<Integer> alreadyChecked = new HashSet<>();

        for (int i = 2; i <= LIMIT_OF_INPUT; i++) {
            if (alreadyChecked.contains(i)) continue;

            int a = sumOfDivisors(i);
            if (i >= a || a > LIMIT_OF_INPUT) continue;

            if (sumOfDivisors(a) == i) {
                amicablePair.add(new int[]{i, a});
                alreadyChecked.add(a);
            }
        }
        return amicablePair;
    }

    public int sumOfDivisors(int n) {
        int limit = (int) Math.sqrt(n);
        int sum = 1;
        for (int i = 2; i <= limit; i++) {
            if (n%i==0) sum += i + (n/i);
        }
        if (limit * limit == n) sum-=limit;
        return sum;
    }
}