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

결과를 StringBuilder로 안하고 +로 하여 시간초과가 계속 나서 고생했던 문제.



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

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    repeat(br.readLine()!!.toInt()) {
        val str = br.readLine()!!
        val res = LinkedList<Char>()
        var now = 0
        for (i in 0 until str.length) {
            when (str[i]) {
                '<' -> if (now != 0) now--
                '>' -> if (now != res.size) now++
                '-' -> if (now != 0 && !res.isEmpty()) res.removeAt(--now)
                else -> res.add(now++, str[i])
            }
        }
        val ans = StringBuilder()
        for (ch in res) {
            ans.append(ch)
        }
        println(ans)
    }
}
cs


저작자표시

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

[BOJ] 백준 9576번 책 나눠주기  (0) 2018.11.22
[BOJ] 백준 11066번 파일 합치기 by Kotlin  (0) 2018.11.21
[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07



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

+ Recent posts

티스토리툴바