[JAVA] 백준 27172 - 수 나누기 게임 (에라토스 테네스의 체)

https://www.acmicpc.net/board/view/108208

 

 

문제 유형은 브루트포스였으나, 이중for문을돌면 5억번을 도므로, 시간초과가 나기때문에

최대한 가지치기를하거나, 중복되는 케이스를 피해야하는데

도저히 떠오르지 않아서 검색을 해보니 에라토스 테네스의 체를 응용하는 문제였다고 한다.

 

 

 

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

public class Main {

    static int[] arr = new int[1000001];
    static int[] num ;
    static int[] ans;
    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] lines = br.readLine().split(" ");
        num = new int[N + 1];
        ans = new int[N + 1];
        for(int i = 1 ; i <= N ; i++){
            num[i] = Integer.parseInt(lines[i - 1]);
            arr[Integer.parseInt(lines[i- 1])] = i;
        }
        for(int me = 1 ; me <= N  ; me++){
            for(int i = num[me] * 2 ; i <= 1000000 ; i += num[me]){
                if(arr[i] > 0){
                    ans[arr[i]]--;
                    ans[me]++;
                }
            }
        }
        for(int i = 1 ; i < N + 1 ; i++){
            System.out.print(ans[i] + " ");
        }

    }


}

 

 

에라토스 테네스의 체를 응용하는 문제는 처음보는것 같아서 그냥 유형을 익혀야 겠다고 생각했다.