백준 [27172] kotlin

문제

https://www.acmicpc.net/problem/27172

풀이

그냥 단순하게 모든 플레이어 간의 대결을 모두 구하여 풀게 된다면 100000! 로 구할 수 없는 문제이다.

그렇다면, 다르게 풀어야 하는데 에라토스테네스의 체를 이용하여 해당 숫자의 배수를 카드 목록에 가지고있다면 , 결투를 하게 진행하면 된다. 

숫자가 담긴 카드 배열을 card라고 하고, 숫자를 가지고 있는지 확인하는 배열을 has라고 했을 때,

card[i] 부터 card[N]까지 배수를 찾아, 가지고 있는 카드인지 확인하여 점수를 계산해주면 된다.

 

코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

private const val MAX_VALUE = 1000001
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))

    val N = br.readLine().toInt()
    val has = MutableList(MAX_VALUE){-1}
    val card = br.readLine().split(" ").map { it.toInt() } as MutableList
    val score = MutableList(N){0}
    card.forEachIndexed { idx, value ->
        has[value] = idx
    }

    repeat(N) {i ->
        // 에라토스테네스의 체
        for(j in card[i] * 2 until MAX_VALUE step(card[i])){
            // 가지고 있다면
            if(has[j] != -1) {
                score[i]++
                score[has[j]]--
            }
        }
    }
    val ans = score.joinToString(" ")
    bw.write(ans)
    bw.flush()
    bw.close()

}