[Baekjoon] 27172_수 나누기 게임

Gold V

문제(출처: https://www.acmicpc.net/problem/27172)

---

< 수 나누기 게임 >

 

문제 풀이 

 

각 카드의 값의 배수가 다른 카드에 존재하는지 확인한다.

 

* 문제에 있는 알고리즘 분류를 먼저 확인했었는데 에라토스테네스의 체가 적혀있었다. 그래서 단순히 에라토스테네스의 체를 사용하여 소수인지 판별하고 카드 두 개의 값이 다 소수라면 무승부인 것을 활용하는 것인 줄 알았다. 직접 값을 나눠서 판단할 경우 시간 초과가 발생했다. 다른 방법이 떠오르지 않아 찾아보니 에라토스테네스의 체 알고리즘 방식처럼 값의 배수를 구하는 것으로 문제를 해결하는 것이었다.

 

 

 my solution (Java)

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

public class _27172_ { // 수 나누기 게임

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		int card[] = new int[n];
		int result[] = new int[1000001];
		boolean arr[] = new boolean[1000001];
		int max = 0;

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			card[i] = Integer.parseInt(st.nextToken());
			arr[card[i]] = true;
			max = Math.max(card[i], max);
		}

		for (int i = 0; i < n; i++) {
			for (int j = card[i] + card[i]; j <= max; j += card[i]) {
				if (arr[j]) {
					result[card[i]] += 1;
					result[j] -= 1;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			bw.write(result[card[i]] + " ");
		}
		bw.flush();
	}
}

변수)
n : 플레이어의 수
card : 플레이어가 가지고 있는 카드에 적힌 수
result : 플레이어의 점수
arr : 가지고 있는 카드 여부
max : 카드의 최댓값

 

플레이어의 수를 입력받는다. 각 플레이어가 가지고 있는 카드에 적힌 수를 입력받아 card 배열에 저장한다. 카드에 적힌 수를 입력받으면서 이 카드 값을 가지고 있다는 것을 나타내기 위해 arr 값을 true로 저장한다. 카드 값 중 최댓값을 구한다.

 

각 플레이어가 가지고 있는 카드를 순환하면서 그 값의 배수를 구한다. 값의 배수가 다른 사람이 가지고 있는 카드 값이라면 자신은 1점을 획득하고 상대방은 1점을 잃는다.

 

최종 각 플레이어의 점수를 출력한다.

---

---