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

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


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
57
58
59
60
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(" "))
    }
}

cs









저작자표시

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

[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06
[BOJ] 1021번 회전하는 큐 - by Kotlin  (0) 2018.10.02
[BOJ] 1068번 트리 byKotlin  (0) 2018.10.02

 쉬운 문제지만 코틀린을 배우는 초기단계라 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

티스토리툴바