백준 9576번 : 책 나눠주기



 설명: 이 문제를 처음에는 이분매칭으로 풀려고 하다가, 이분매칭보다는 그냥 Greedy하게 풀면 풀리겠다고 생각해서

      그리디로 해결하였다.


    List에 사람 각각의 (a,b)를 Pair로 저장해준다. 그리고 Sorting한다.

Sorting의 기준은 b의 오른차순으로 정렬했으며, b가 똑같은 경우 a가 작은 것이 앞에 오도록 정렬하였다.


(만약 input이 

1                이라면 소팅 된 후의 값은   

5 5 (n,m)           

2 4                            1 2

3 4                           1 3

3 3                           3 3

1 2                           2 4

1 3                           3 4

)

 정렬 후 List의 처음부터 한명씩 확인한다.

그리고 그 사람의 a와 b사이를 확인하면서 가져갈 수 있는 책이 존재하면 가져가도록 하고

그 index의 visit을 true로 바꿔준다.


 핵심은 정렬의 기준을 잡고 정렬 후 이중for문을 돌면서 확인해서 책을 가져가는 것이라고 생각한다.



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

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    data class Pair(val s: Int, val e: Int) : Comparable<Pair> {
        override fun compareTo(other: Pair): Int {
            if (this.e != other.e) return this.e - other.e
            return this.s - other.s
        }
    }
    repeat(br.readLine()!!.toInt()) {
        val (n, m) = br.readLine()!!.split(" ").map { it.toInt() }
        val list = Array(m) {
            val (s, e) = br.readLine()!!.split(" ").map { it.toInt() - 1 }
            Pair(s, e)
        }
        list.sort()
        
        val visit = BooleanArray(n)
        var res = 0
        for (i in 0 until m) {
            for (j in list[i].s..list[i].e) {
                if (!visit[j]) {
                    visit[j] = true
                    res++
                    break
                }
            }
        }
        println(res)
    }
}
cs









저작자표시

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

[BOJ] 1952번 달팽이2  (0) 2018.12.31
[BOJ] 백준 11066번 파일 합치기 by Kotlin  (0) 2018.11.21
[BOJ] 백준 5397번 키로거 by Kotlin  (0) 2018.11.20
[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13

DP문제.


점화식은    dp[i][j] => i~j 까지의 최소 비용

dp[i][j]= min(dp[i][j], dp[i][k] + dp[k+1][j])    => 합친 값의 최소값을 선택. k는 i와 j의 사이값들 모두 확인해야한다.

dp[i][j]+=sum[j]-sum[j-1]   (i부터 j까지의 합 추가로 더해줘야함)


O(n^3)


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


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
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

fun main(args: Array<String>) {
    val br= BufferedReader(InputStreamReader(System.`in`))
    
repeat(br.readLine()!!.toInt()){
        val n=br.readLine()!!.toInt()
        val arr=br.readLine()!!.split(" ").map { it.toInt() }.toIntArray()
        val dp=Array(n){IntArray(n)}
        val sum=IntArray(n)
        sum[0]=arr[0]
        for(i in 1 until n)  sum[i]=sum[i-1]+arr[i]
        
        for(j in 1 until n){
            for(i in j-1 downTo 0){
                dp[i][j]=987654321
                for(k in i until j){
                    dp[i][j]= min(dp[i][j],dp[i][k]+dp[k+1][j])
                }
                if(i!=0)    dp[i][j]+=sum[j]-sum[i-1]
                else    dp[i][j]+=sum[j]
            }
        }
        println(dp[0][n-1])
    }
}
cs


저작자표시

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

[BOJ] 1952번 달팽이2  (0) 2018.12.31
[BOJ] 백준 9576번 책 나눠주기  (0) 2018.11.22
[BOJ] 백준 5397번 키로거 by Kotlin  (0) 2018.11.20
[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13



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


fun main(args: Array<String>) {
    val br=BufferedReader(InputStreamReader(System.`in`))
    val (m,n,l)=br.readLine()!!.split(" ").map { it.toInt() }
    val saro=br.readLine()!!.split(" ").map { it.toInt() }.sorted()
    val animal=Array(n){ val (x,y)=br.readLine()!!.split(" ").map { it.toInt() }
        Pair(x,y) }
    var res=0

    for(i in 0 until n){
        val (x,y)=animal[i]
        if(y>l) continue    // y값이 l보다 커지면 사대의 x좌표에 상관없이 도달 할 수 없음.
        var left=0
        var right=m-1
        while(left<=right){     // 동물의 x좌표를 가지고 사대를 이진탐색
            val mid=(left+right)/2
            if(saro[mid] in x-(l-y)..x+(l-y)){  // 동물의 x좌표에서 양옆으로 (l-y)만큼 떨어져있으면
//사냥가능하다
                res++
                break
            }
            if(saro[mid]<x-(y-l))   left=mid+1
            else    right=mid-1
        }
    }
    println(res)
}

cs


저작자표시

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

[BOJ] 백준 11066번 파일 합치기 by Kotlin  (0) 2018.11.21
[BOJ] 백준 5397번 키로거 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06

백준 2170번 선 긋기


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



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

fun main(args: Array<String>) {
    val br=BufferedReader(InputStreamReader(System.`in`))
    val n=br.readLine()!!.toInt()
    data class Pair(val start:Int,val end:Int):Comparable<Pair>{
        override fun compareTo(other: Pair): Int {
            return this.start.compareTo(other.start)
        }
    }
    val line=Array(n){ val (start,fin)=br.readLine()!!.split(" ").map { it.toInt() }
        Pair(start,fin)
    }
    line.sort()
    var now=line[0].start
    var res=0
    for(i in 0 until n){
        if(line[i].end>now){
            res += if(now>=line[i].start) {
                Math.abs(line[i].end - now)
            } else{
                Math.abs(line[i].end-line[i].start)
            }
            now = line[i].end
        }
    }
    println(res)
}
cs


저작자표시

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

[BOJ] 백준 5397번 키로거 by Kotlin  (0) 2018.11.20
[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06
[BOJ] 1021번 회전하는 큐 - by Kotlin  (0) 2018.10.02

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

 쉬운 문제지만 코틀린을 배우는 초기단계라 review 하겠습니다


 해결방법 : "CAMBRIDGE" 에 들어간 알파벳을 input에서 빼고 출력하는 문제입니다. 

대문자만 필요하므로 크기 26짜리 배열 alpha를 Boolean 배열로 선언하고, 

"CAMBRIDGE"의 알파벳 하나하나의 자리에 true로 하였습니다.

그리고 입력받은 input에 filter을 통해 true가 아닌것 (즉, false 인 것)만 출력하도록 하였습니다.


 ▼ 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.io.BufferedReader
import java.io.InputStreamReader
 
fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val chk = "CAMBRIDGE"
    val alpha = BooleanArray(26)
    chk.forEach { alpha[it.toInt() - 65] = true }
 
    val input = br.readLine()
    input.filter { !alpha[it.toInt() - 65] }.forEach { print(it) }
    println()
}
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] 1068번 트리 byKotlin  (0) 2018.10.02

+ Recent posts

티스토리툴바