[백준 20366] - 같이 눈사람 만들래?(Kotlin)[골드3]

문제

https://www.acmicpc.net/problem/20366

20366번: 같이 눈사람 만들래?

 

문제 풀이

4가지 경우의 수를 모두 구한다면 아마 시간 초과를 피할 수 없을 것이다.

해당 문제도 투 포인터 알고리즘을 사용해야 한다.

눈사람을 4개 골라야 하는데 투 포인터 알고리즘으로 어떻게 하냐~~ 할 수 있는데 

세 용액 문제와 동일하게 탐색 숫자를 줄여주면 된다.

4개를 골라야 한다면 이미 2개를 고르고 나서 나머지 2개에 대해서 투 포인터 알고리즘을 사용하면 된다.

나는 2개의 눈덩이를 고르기 위해서 조합을 사용했고, 2개를 뽑았다면 거기서 투 포인터 알고리즘을 사용했다.

범위를 탐색하면서 start가 이미 선택한 눈덩이를 가리킨다면 start를 한 칸 증가시켜 주고,

end가 이미 선택한 눈덩이를 가리킨다면 end를 한 칸 감소시켜 줬다.

진행하다가 두 눈사람의 높이 차이가 0이라면 그 즉시 탐색을 멈췄다.

경우의 수가 아닌 최솟값을 출력하면 되기 때문이다.

 

 

전체 코드

package TwoPointer.`20366_같이_눈사람_만들래?`.LJH

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.abs
import kotlin.math.min

class `20366` {
    private var n = 0
    private lateinit var array : List<Long>
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private val comb  = arrayOf(0,0)
    private var sum = 2000000001L
    init{
        input()
    }
    fun input(){
        n = br.readLine().toInt()
        array = br.readLine().split(" ").map { it.toLong() }.sorted()
        makeCombination(0,0,2)
        println(abs(sum))
    }
    private fun makeCombination(cnt : Int , depth : Int, limit : Int){
        if(cnt == limit){
            search()
            return
        }
        for(i in depth until n){
            comb[cnt] = i
            makeCombination(cnt+1,i+1,limit)
            comb[cnt]=0
        }
    }
    private fun search(){
        var start = 0
        var end = n-1
        while(start<end){
            if(comb.contains(start)){
                start++
                continue
            }
            if(comb.contains(end)){
                end--
                continue
            }
            val result = array[comb[0]]+array[comb[1]]- (array[start]+array[end])
            sum = min(abs(sum),abs(result))
            if(result == 0L)
                break
            if(result<0) {
                end--
            } else {
                start++
            }
        }
    }
}

fun main(){
    val solution = `20366`()
}