[백준] 27172. 수 나누기 게임 (완전탐색/Java)

[백준] 27172. 수 나누기 게임

 

📌 풀이 과정

처음엔 모든 플레이어 쌍을 비교하는 O(N^2) 방식을 생각했지만, 시간 초과가 떴다...🥹

문제를 다시 보면 "자신의" 카드가 상대방의 카드의 약수인 경우, "자신은" 1점을 얻고 상대는 1점을 잃게 된다.

즉, 약수-배수 관계를 이용해서 더 효율적으로 풀 수 있다!!

1. 각 카드 숫자의 약수를 찾아 관계를 파악한다.
2. 제곱근 까지만 검사하여 약수 탐색을 최적화 한다.
3. 약수 관계가 있을 때마다 약수(나누는 숫자)는 점수를 얻고, 나눠지는 숫자는 점수를 잃는다.

제곱근까지만 검사하여 약수 찾기!

예를 들어, 숫자 24의 약수를 찾는 경우

• 일반적인 방법: 1 ~ 24까지 모든 숫자 확인 (24번 연산)
• 제곱근 활용: 1부터 √24인 약 4.9까지만 확인 (5번 연산)

24의 약수 = 1, 2, 3, 4, 6, 8, 12, 24

 

모든 약수는 항상 쌍으로 존재하기 때문에

한쌍 중 하나는 반드시 √N 이하, 다른 하나는 √N 이상이다.

따라서 √N까지만 검사하고 찾은 약수의 짝을 계산하면 모든 약수를 찾을 수 있다.

 

✨ 제출 코드

메모리: 38032 KB

시간: 876 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] cards = new int[N];
        int[] score = new int[1000001]; // 각 번호에 대한 점수
        boolean[] visited = new boolean[1000001]; // 숫자 존재 여부

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            cards[i] = Integer.parseInt(st.nextToken());
            visited[cards[i]] = true;
        }

        for(int i = 0; i < N; i++){
            int tmp = cards[i];
            for(int j = 1; j <= (int)Math.sqrt(tmp); j++){
                if(tmp % j == 0){ // j가 tmp의 약수인 경우
                    if(visited[j]){
                        score[j] += 1;
                        score[tmp] -= 1;
                    }
                    if(j * j != tmp && visited[tmp/j]){
                        score[tmp/j] += 1;
                        score[tmp] -= 1;
                    }
                }
            }
        }


        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++){
            sb.append(score[cards[i]] + " ");
        }
        System.out.println(sb);
    }

}