글 읽기 - (해결) 확인부탁드립니다. 틀린코드->맞았습니다

limdongjin 1년 전 0

자문자답이지만,해결했습니다

기지국 두개 만들면 최소 비용을 얻을 수 있었네요. 잘못 생각했었네요

------이전 질문--

제가 문제 이해를 잘못한걸수도 있지만, 확인 부탁드립니다.

-2 10

1000 1

ANS: 501 이 나와야 정상이라고 생각합니다.

(-2, 10), (1000, 1) 건물을 포함하는 통신을 만드려면, (1000-(-2))/2=1002/2 = 501 만큼의 설치 비용이 필요합니다.

하지만, 아래의 코드를 제출하였을때는 "맞았습니다" 처리되는데 이 코드는 위의 입력에 대해서 22 를 출력합니다.

반면 정상적인 결과(501) 을 출력하도록 코드를 수정한 후 제출하였으나, 해당 코드는 "틀렸습니다"로 처리됩니다.

package main.kotlin

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min
import kotlin.time.Duration.Companion.seconds

// x, y
typealias Pos = Pair<Int, Int>
const val INF = 987654321

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val buildings = List<Pos>(n) {
        readLine().split(" ").map(String::toInt)
            .run { this[0] to abs(this[1]) } // 음수 y값은 양수로 바꿔도 무방하다.
    }

    println(solve(n, buildings))
}

fun solve(n: Int, buildings: List<Pos>): Int {
    val sorted = buildings.sortedBy { it.first }

    // int dp[n+1]
    // dp[k] = 0~k 번째 건물 까지 포함 하도록 하는 최소 비용
    val dp = IntArray(n+1) { INF }
        .apply {
            this[0] = 0

            // dp[1] : 1 번째 건물까지 포함하도록 하는 최소 비용 후보 = (0번째 건물의 높이)*2
            this[1] = sorted[0].second * 2
        }
     // 아래의 이프문을 추가하면 " 틀렸습니다"
     // 반면 이프문을 주석처리하면 "맞았습니다"
    // if(n==2) return max(sorted[0].second*2, (sorted[1].first-sorted[0].first)/2)
    
    for(cur in 2..n){
        // cur 번째 건물에 대한 dp 를 구하자.
        val prev = cur - 1

        // h: 최대 높이
//        var h = sorted[prev].second
//        println("cur: $cur, prev: $prev")
//        println(dp.toList())

        var maxHeight = sorted[prev].second

        for(other in prev downTo 0){
            // maxHeight = other 번째 부터 prev 번째 건물의 높이 중 최대 높이
            maxHeight = max(maxHeight, sorted[other].second)

            // distanceX: prev 건물과 other 건물 사이의 x 축 거리
            //            sorted[prev].first - sorted[other].first
            val distanceX = sorted[prev].first - sorted[other].first

            // prev 와 other 건물을 포함 하기 위해 필요한 통신폭
            val cWidth = max(maxHeight * 2, distanceX)

            // cWidth + dp[other] = prev 와 other 건물을 포함하는 통신폭 + 0~other 건물까지 포함하는 최소 비용
            val candidate = cWidth + dp[other]

            dp[cur] = min(dp[cur], candidate)
        }
    }

    return dp[n]
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(해결) 확인부탁드립니다. 틀린코드->맞았습니다

limdongjin 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말