[BOJ] 백준 27172 수 나누기 게임 (자바)

[BOJ] 자바 27172 수 나누기 게임 (링크)

풀이

알고리즘 분류를 보면 에라토스테네스의 체가 있다.
이는 에라토스테네스의 체를 이용하여 소수를 구하는 것처럼 풀라는 것이다.

예제 1의 경우 배열 X를 다음과 같다고 하자.

이제 이 배열의 값과 인덱스를 뒤바꾼 배열 pos를 만들자.

배열의 초기화가 0이기 때문에 0번째 인덱스를 표현하기 위해 1을 더하고 저장한다.

이후 배열 X를 돌면서 각 값의 배수 인덱스의 값이 0이 아니면 점수를 증감하자.

최종 코드 및 결과

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));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine()), X[] = new int[N], INF = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) INF = Math.max(INF, X[i] = Integer.parseInt(st.nextToken()));
		
		int[] P = new int[N+1], pos = new int[INF+1];
		for(int i = 0; i < N; i++) pos[X[i]] = i+1;

		for(int mod : X) for(int i = mod*2; i <= INF; i += mod) {
        	if (pos[i] != 0) {
            	P[pos[i]]--;
                P[pos[mod]]++;
            }
        }
		for(int i = 1; i <= N; i++) sb.append(P[i]).append(" ");
		System.out.print(sb);
	}
}