[백준/JAVA] 27172_수 나누기 게임

백준🔗

27172번: 수 나누기 게임

 

문제

 

 

 

간단 풀이

에라토스테네스의 체는 소수를 찾는 가장 빠르고 간단한 알고리즘이다. 

1부터 N까지의 수 중에서 소수를 찾는다고 하면 1 제외, 2의 배수 제외, 3의 배수 제외 .... (√N 이하 중 최대 정수)의 배수 제외 이렇게 하면 된다.

그래서 알고리즘 분류만 보고 이 문제에서 소수를 어떻게 활용해야 하지 한참 고민했지만...

이 문제는 소수를 활용하는 문제는 아니고 에라토스테네스의 체의 원리를 응용하는 문제였다.

 

플레이어들이 가진 카드 번호를 입력받을 때 2가지 배열에 함께 저장한다.

1) 인덱스 : 플레이어 번호 / 값 : 카드 번호

2) 인덱스 : 카드 번호 / 값 : 플레이어 번호

=> 1번 배열에서 각 카드 번호의 배수들이 존재하는지 여부를 2번 배열을 통해 확인

     존재한다면 플레이어들의 점수 업데이트

 

⭐⭐한 가지 주의할 점!! 

2번 배열의 초기값이 0으로 채워져 있는데 플레이어 번호를 0부터 시작한다면 둘을 구분할 수 없기 때문에 틀리는 경우가 발생한다.

1) 2번 배열 초기값 0, 플레이어 번호 1부터 시작

2) 2번 배열 초기값 -1(적당한 음수), 플레이어 번호 0부터 시작

이런 식으로 적절히 둘을 구분해주기 위한 조치를 해줘야 한다! (이거 때문에 한 번 틀렸다..)

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine()); // 플레이어 수
		int[] cards = new int[N + 1];
		int[] index = new int[1000001];
		int[] score = new int[N + 1];
		// 플레이어가 가지고 있는 카드 번호 입력받기
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			cards[i] = Integer.parseInt(st.nextToken());
			index[cards[i]] = i;
		}
		// 앞에서부터 해당 카드 번호로 나누어떨어지는 카드 번호가 있는지 인덱스로 탐색
		for (int i = 1; i <= N; i++) {
			for (int idx = cards[i] * 2; idx <= 1000000; idx += cards[i]) {
				if (index[idx] >= 1) {
					score[index[idx]]--;
					score[i]++;
				}
			}
		}
		for (int i = 1; i <= N; i++) {
			bw.write(score[i] + " ");
		}
		bw.flush();
		br.close();
		bw.close();
	}
}

 

참고 자료

[백준 C++] 27172번: 수 나누기 게임