[백준] 1241번. 머리 톡톡(JAVA)

문제

https://www.acmicpc.net/problem/1241

---

풀이(15분)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int[] numbers = new int[n + 1];
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        
        for (int i = 1; i <= n; i++) {
            int inputNumber = Integer.valueOf(br.readLine());
            numbers[i] = inputNumber;
            frequencyMap.put(inputNumber, frequencyMap.getOrDefault(inputNumber, 0) + 1);
        }

        int[] divisorCount = new int[1_000_001];
        for (int num : frequencyMap.keySet()) {
            int count = 0;

            if (num <= 1) {
                count = frequencyMap.get(num) - 1;
            } else {
                for (int i = 1; i <= Math.sqrt(num); i++) {
                    if (num % i == 0) {
                        if (frequencyMap.containsKey(i)) count += frequencyMap.get(i);
                        int pair = num / i;
                        if (frequencyMap.containsKey(pair)) {
                            count += frequencyMap.get(pair);
                            if (pair == num) count--;
                            if (pair == i) count -= frequencyMap.get(i);
                        }
                    }
                }
            }
            divisorCount[num] = count;
        }

        for (int i = 1; i <= n; i++) {
            System.out.println(divisorCount[numbers[i]]);
        }
    }
}

---

문제 풀이 전략

 

사용된 자료구조보다는 아이디어가 중요한 문제 같아 그 부분에 초점을 두고 풀어보자.

 

숫자를 입력받았을 때, 자기를 때릴 수 있는 수들을 계산하는 것이다.

즉, 약수를 구하자는 것이다.

 

n = 100,000으로 이미 크다. 거기에 숫자도 1,000,000까지 가능하니 모두 탐색하는 것은 불가능하다.

하지만 에라토스테네스의 체와 동일한 원리로 약수를 찾을 때도 제곱근까지만 해도 된다는 것을 알아야 한다.

-> 모든 자연수는 (제곱근) * (제곱근) 의 조합을 갖게 된다. 이 경우 두 수의 곱 중 반드시 하나는 제곱근 이하의 수가 된다.

-> 한 쪽의 수를 제곱근 범위까지만 탐색하면 된다!

 

위와 같은 원리로 인해 제곱근까지만 탐색을 한 뒤, map에 저장하여 정답을 탐색하면 된다.