백준 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

[BOJ] 1021번 회전하는 큐


문제 : 원형 큐에서 현재 위치에서 목적 위치까지 가는데 가장 가까운 방법으로 가는데 드는 비용의 합.



설명 : 큐에 1~N까지 원소를 넣고,  현재 위치는 큐의 첫번째 원소로 생각.

  ( 큐의 첫번째 위치에서 +1 ,  큐의 끝점에서 -1 ) => 반복해서 도착하고자 하는 번호에 먼저 도달하는 것이 비용이 작게 든다. 따라서 먼저 도달한 방법으로   큐의 현재위치(q[0]) 를 이동시킨다.


 만약 현재위치에서 좌측으로 가는 것이 빠르다 => q[0]에 큐의 마지막 원소를 넣고, 마지막 원소를 삭제 : 즉, 좌측으로 이동.

 만약 현재위치에서 우측으로 가는 것이 빠르다 => 큐에 q[0]를 뒤에 추가하고, q[0]를 삭제 : 즉 q[0]를 우측으로 이동

 

 그리고 한칸이동 시 비용을  +1 해주어서 결과값을 얻었다.



(문제 바로가기 : https://boj.kr/1021 )


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
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n, m) = br.readLine()!!.split(" ").map { it.toInt() }
    val choice = br.readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    val q = LinkedList<Int>()
    for (i in 1..n) q.add(i)
    var res = 0
    var count = 0
    while (count != m) {
        if (q.first == choice[count]) {
            q.poll()
        } 
        else {
            for (i in 1 until q.size) {
                if (q[q.size - i] == choice[count]) {
                    while (q[0] != choice[count]) {
                        q.add(0, q.last)
                        q.removeLast()
                        res++
                    }
                    q.poll()
                    break
                } else if (q[i] == choice[count]) {
                    while (q[0] != choice[count]) {
                        q.add(q.first)
                        q.removeFirst()
                        res++
                    }
                    q.poll()
                    break
                }
            }
        }
        count++
    }
    println(res)
}
cs




저작자표시

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

[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06
[BOJ] 1068번 트리 byKotlin  (0) 2018.10.02
BOJ 2789번 유학금지 by Kotlin  (0) 2018.07.18

BOJ(백준) 1068번 트리



문제 : 입력으로 주어진 트리에서 한 노드를 지웠을 때, 남은 트리에서 리프 노드 개수 구하기.


설명: 

 루트부터 자식들을 BFS로 계속 찾아가는 방법으로 풀었다. 각 노드에 방문시 확인해주면서 leaf 노드의 개수를 추가한다.

 확인하는 것 = 1. 만약 자식의 개수가 1개고, 그 자식이 삭제한 노드이면 . Leaf 노드 이므로 결과값에 +1

                    2. 만약 자식이 없으면 Leaf 노드이므로 결과값에 +1  

 

 

 주어진 입력에서 각 노드의 부모를 배열로 입력받는다.  ex) -1 0 0 1 1   --> 0번 노드는 root이고,  1번,2번 노드의 부모는 0번 노드이고, 3,4번 노드의 부모는 1번 노드이다. 

=> 이 입력을 바꾸어서, parent node 번호에 자식 node 번호를 저장한다.

  adj[노드 번호] 에는 해당 노드의 자식 번호들이 저장되어있다.



(문제 바로가기 : boj.kr/1068)



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
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 adj = Array(n) { LinkedList<Int>() }
    var root = 0
    var tmp = 0
    val st = StringTokenizer(br.readLine()!!)
    while (st.hasMoreTokens()) {
        val parent = st.nextToken().toInt()
        if (parent != -1) {
            adj[parent].add(tmp++)
        } else root = tmp++
    }
    val remove = br.readLine()!!.toInt()
 
    val q = LinkedList<Int>()
    var res = 0
    q.add(root)
    while (!q.isEmpty()) {
        val here = q.poll()
        if (here == remove) continue
        if (adj[here].size == 0 || (adj[here].size == 1 && adj[here][0] == remove)) {
            res++
            continue
        }
        for (next in adj[here]) {
            if (next != remove) {
                q.add(next)
            }
        }
    }
    println(res)
}
cs


저작자표시 비영리 변경금지

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

[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06
[BOJ] 1021번 회전하는 큐 - by Kotlin  (0) 2018.10.02
BOJ 2789번 유학금지 by Kotlin  (0) 2018.07.18

+ Recent posts

티스토리툴바