백준 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 |
.png)
.png)
.png)
