[2023-04-15] 1461 도서관 (Kotlin) + 1문제

 

 

문제 링크: https://www.acmicpc.net/problem/1461

1461번: 도서관

 

개인적으로는 규칙을 찾느라 힘들었습니다.

 

각각의 입력 케이스에 대해 답안을 찾아보며 다음과 같은 가설을 세웠습니다.

 

// 1. 전체의 리스트에서 m으로 나누어 떨어지는지, 아닌지 판단
// 2. 나누어 떨어질 경우, 그대로 정렬하여 계산 (입력 3)
// 3. 아닐 경우, plus minus로 나눔
// 4. plus minus 각각 나누어 떨어지는지 판단, 나누어 떨어지지 않을 경우 나머지의 경우만 계산
// 이 때 나머지의 경우는 절대값이 최소의 값으로 계산
// 5. 계산한 것을 빼고 다 각각 계산
// 6. 절대값이 가장 큰 경우는 마지막으로 미뤄두어, 복귀하는 경우가 없어야함
//    따라서 마지막에 절대값이 가장 큰 경우를 빼줌

//    첫 번째 케이스
//    7 2
//    -37 2 -6 -39 -29 11 -28

//    나누어 떨어지지 않으므로 plus minus로 나눔
//    minus의 개수가 2로 나누어 떨어지지 않으므로, 나머지인 1 만큼 절대값이 최소인 값으로 계산
//    -6이 최소이므로 -6 1번 게산
//    이제 minus plus 둘 다 나누어 떨어지므로 모두 2개씩 계산
//    마지막에 절대값이 가장 큰 39를 빼줌

//           -37,-39   -6     2, 11      -28,-29    
//    println(37+2+    6+6   +2+9+11    +28+1+29) 131

//    두 번째 케이스
//    8 3
//	  -18 -9 -4 50 22 -26 40 -45   

//    나누어 떨어지지 않으므로 plus minus로 나눔
//    minus 개수가 3개로 나누어 떨어지지 않으므로, 나머지인 2만큼 절대값이 최소인 값으로 계산
//    -4, -9가 최소이므로 2개 계산
//    이제 minus plus 둘 다 나누어 떨어지므로 모두 3개씩 계산
//    마지막에 절대값이 가장 큰 50을 빼줌

			 -4,-9   -18,-26,-45    22,40,50
//    println(4+5+9  +18+8+19+45  +22+18+10)

//    세번 째 케이스
//    6 2
//    3 4 5 6 11 -1

//    나누어 떨어지므로 그대로 정렬 (-1, 3, 4, 5, 6, 11)
//    그대로 두 개씩 계산
//    마지막에 절대값이 가장 큰 11을 빼줌
              -1,3   4,5    6,11
//    println(1+4+3 +4+1+5 +6+5)

 

출력 예시가 모두 일치하였지만, 틀렸다는 결과가 나왔습니다.

 

다시 고민을 해봤고, 그냥 양수, 음수로 나눠도 성립을 한다는 것을 깨달았습니다.

 

 

// 규칙
// 1. plus minus로 나눔
// 2. plus minus 각각 나누어 떨어지는지 판단, 나누어 떨어지지 않을 경우 나머지의 경우만
//    최소의 경우를 계산
// 3. 계산한 것을 빼고 다 각각 계산
// 4. 가장 큰 값을 마지막에 빼줌

 

결과 코드입니다.

 

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val list = br.readLine().split(' ').map{it.toInt()}
    // 양수부, 음수부로 나눠줌
    val plus = LinkedList<Int>()
    val minus = LinkedList<Int>()
    for (index in list.indices){
        if (list[index] > 0)
            plus.add(list[index])
        else
            minus.add(list[index])
    }
    plus.sort()
    minus.sort()
    
    var sum1 = 0 // minus 에서 나누어 떨어지지 않을 경우
    if (minus.size % m != 0) {
        val v = minus.size % m // 나머지 값
        var last = minus.last()
        for (index in 0 until v) { // 나머지 값만큼 최소 거리 계산
            if (index == 0) {
                sum1 = Math.abs(last)
                minus.removeLast()
            } else {
                sum1 += Math.abs(last - minus.last())
                last = minus.removeLast()
            }
        }
        sum1 += Math.abs(last)
    }

    var sum2 = 0 // plus에서 나누어 떨어지지 않을 경우
    if (plus.size % m != 0) {
        val v = plus.size % m // 나머지 값
        var first = plus.first()
        for (index in 0 until v) { // 나머지 값만큼 최소거리 계산
            if (index == 0) {
                sum2 = first
                plus.removeFirst()
            } else {
                sum2 += Math.abs(first - plus.first())
                first = plus.removeFirst()
            }
        }
        sum2 += first
    }
    
    var sum3 = 0 // 나머지 음수부 계산
    var i1 = 0
    while (minus.isNotEmpty()){
        i1++
        if (i1 == m){
            sum3 += Math.abs(minus.removeLast()*2)
            i1 = 0
        }
        else
            minus.removeLast()
    }
    
    var sum4 = 0 // 나머지 양수부 계산
    var i2 = 0
    while (plus.isNotEmpty()) {
        i2++
        if (i2 == m) {
            sum4 += plus.removeFirst() * 2
            i2 = 0
        } else
            plus.removeFirst()
    }
	//                                           마지막에 가장 절대값이 큰 값 빼기
    println(sum1 + sum2 + sum3 + sum4 - Math.max(list.max(), Math.abs(list.min())))
}