백준 1671번 상어의 저녁식사.


문제 설명

 

 크기, 속도, 지능 모두 크거나 같으면  i -> j 가 먹을 수 있다.  =  "i 에서 j로 갈 수 있다" 

즉, 먹을 수 있는 간선들을 모두 만들면 이분 매칭 문제와 같다.

 

 주의할 점은 크기, 속도, 지능 모두 같으면 서로 잡아먹어서 0이 될 수도 있으므로

상어 한마리가 또다른 한마리만 먹을 수 있도록 설정했다.

 ex)  크기: 10 속도:10 지능:10 인 상어 2마리(i,j) 가 있을 때  i는 j를 잡아 먹을 수 있지만 j는 i를 잡아먹지 못하도록 설정했다.



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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    data class Shark(val size:Int,val speed:Int,val intel:Int):Comparable<Shark>{
        override fun compareTo(other: Shark): Int {
            if(size==other.size&&speed==other.speed&&intel==other.intel)    return 0
            if(size>=other.size&&speed>=other.speed&&intel>=other.intel)    return 1
            return -1
        }
    }
    val br=BufferedReader(InputStreamReader(System.`in`))
    val list=ArrayList<Shark>()
    val n=br.readLine()!!.toInt()
    var visit=BooleanArray(n)
    val B=IntArray(n){-1}
    val adj=Array(n){ LinkedList<Int>() }
    repeat(n){
        val (size,speed,intel)=br.readLine()!!.split(" ").map { it.toInt() }
        list.add(Shark(size,speed,intel))
    }
    
    for(i in 0 until n){
        for(j in 0 until n){
            if(i==j)    continue
            if(list[i]==list[j]&&i>j){
                adj[i].add(j)
            }
            else if(list[i]>list[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
    }
    
    var count=0
    for(i in 0 until n){
        visit.fill(false)
        if(go(i))   count++
        visit.fill(false)
        if(go(i))   count++
    }
    println(n-count)
}
cs


저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1021번 회전하는 큐 - by Kotlin  (0) 2018.10.02
[BOJ] 1068번 트리 byKotlin  (0) 2018.10.02
BOJ 2789번 유학금지 by Kotlin  (0) 2018.07.18

+ Recent posts

티스토리툴바