글 읽기 - [파라메트릭 서치] 어떤 경우에 ans 값을 갱신시키는지 잘 모르겠습니다.

linear114 2년 전 0

파라메트릭 서치를 통해 문제 해결을 시도했습니다.

Case 1번으로 제출을 했을때는 정답이 되는데,

Case 2번으로 제출을 하면, 오답처리가 됩니다.

(둘의 차이는 ans값을 갱신하는 조건의 차이뿐입니다.)

제 생각으로는, 어쨌든 count라는 값이 문제에서 원하는 공유기 갯수(c)와 일치하는 순간이 무조건 발생해야 된다고 생각을 했습니다.

그래서 Case2번으로 문제풀이를 했던건데, 해결이 안되어서 당황스러웠습니다.

Case2번이 안되는 이유 혹은 반례를 알려주시면 정말 감사할 것 같습니다.

private fun main() {
    val (n, c) = readLine()!!.split(" ").map { it.toInt() }
    val arr = Array(n) { readLine()!!.toInt() }
    arr.sort()

    var start = 1
    var end = arr[n-1] - arr[0]
    var ans = arr[1] - arr[0]

    while(start <= end) {
        var currentPos = arr[0]
        val mid = (start + end) / 2
        var count = 1   // 설치 가능한 공유기의 수

        for(i in 1 until n) {
            val distance = arr[i] - currentPos

            if(distance >= mid) {
                currentPos = arr[i]
                count++
            }
        }

        // CASE 1. Count >= c 에서 ans값 갱신
        if(count >= c) {
            start = mid + 1
            ans = mid
        } else if(count < c) {
            end = mid - 1
        }

        // CASE 2. Count == c 에서 ans값 갱신
        if(count >= c) {
            start = mid + 1
        } else if(count < c) {
            end = mid - 1
        }
        
        if(count == c) {
            ans = mid
        }
    }

    println(ans)
}

wogus23 2년 전 0

구체적인 반례는 떠오르지 않는데 만약 처음의 mid 값이 유일한 해이고, count>=c인 상태이면 33번 조건에 의해 start=mid+1로 다시 탐색을 진행합니다. 이 과정에서 ans는 갱신이 한번도 안됐기 때문에 답이 안 나올 것 같아요!

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

문제

문제

출처

ICPC

[파라메트릭 서치] 어떤 경우에 ans 값을 갱신시키는지 잘 모르겠습니다.

linear114 2년 전 0

wogus23 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말