'1017' 태그의 글 목록

1017

2018. 10. 7. 22:45

백준 1017번 소수 쌍

문제 설명

각 수에 대해 다른 수와 합이 소수이면 선택 가능하도록 간선을 만들어준다.

그리고 첫번째 수에 가능한 수를 하나씩 고정시켜놓고, 나머지를 이분매칭 시켜서 모두 매칭이 되면 res에 추가.

1) 두 수의 합이 최대 2000까지이므로 에라토스테네스의 체로 2000까지 Boolean Array로 감별

2) 하나의 숫자에 대해 다른 숫자와의 합이 소수이면 간선 추가.

3) adj[0][0] , adj[0][1] ... adj[0][adj.size-1] 에 대해

각각 B[adj[0][i]]=0 (즉, 첫번째 수와 i번째 수를 매칭시킴)

그리고 나머지에 대해 이분매칭

문제 바로가기 : boj.kr/1017

import java.io.BufferedReader

import java.io.InputStreamReader

import java.util.*

fun main(args: Array<String>) {

    val br= BufferedReader(InputStreamReader(System.`in`))

    val n=br.readLine()!!.toInt()

    val arr=br.readLine()!!.split(" ").map { it.toInt() }

    val chkPrimeNum=BooleanArray(2001){true}

    val adj=Array(n){ LinkedList<Int>() }

    val visit=BooleanArray(n)

    val B=IntArray(n){-1}

    chkPrimeNum[1]=false

    for(i in 2..2000){       // 에라토스테네스의 체로 2000까지

        var j=2

        if(chkPrimeNum[i]) {

            while (i * j <= 2000) {

                chkPrimeNum[i*j]=false

j++

}

}

}

    for(i in 0 until n){     //간선 연결

        for(j in 0 until n){

            if(i==j)    continue

            if(chkPrimeNum[arr[i]+arr[j]]){

                adj[i].add(j)

}

}

}

    fun go(here:Int):Boolean{

        if(visit[here]) return false

        visit[here]=true

        for(there in adj[here]){

            if(B[there]==-1||go(B[there])){

                B[there]=here

                return true

}

}

        return false

}

    val res=LinkedList<Int>()

    for(i in 0 until adj[0].size){

        B.fill(-1)

        B[adj[0][i]]=0

        var count=1

        for(j in 1 until n){

            visit.fill(false)

            visit[0]=true

            if(go(j))   count++

            else break

}

        if(count==n) res.add(arr[adj[0][i]])

}

    if(res.isEmpty())   println(-1)

    else{

        res.sort()

        println(res.joinToString(" "))

}

}

PREV 1 NEXT