[파이썬 알고리즘 문제풀이 입문] 이분탐색(결정알고리즘) & 그리디 알고리즘 - 랜선자르기

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.
편의를 위해 랜선을 자를 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def Count(mid):
    count = 0
    for i in lines:
        count += (i//mid)
    return count

K, N = map(int, input().split())
lines = list()
largest = 0

for i in range(K):
    lines.append(int(input()))

largest = max(lines)

lt = 1
rt = largest

while lt<=rt:
    mid = (lt+rt)//2
    if Count(mid) >= N:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1

print(res)

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

import java.io.*
import java.util.*

val lines : MutableList<Int> = mutableListOf()

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val (K, N) = readLine().split(" ").map { it.toInt() }
    for(i in 0 until K) {
        lines.add(readLine().toInt())
    }

    var largest = lines.max()
    var lt = 1
    var rt = largest
    var mid = 0
    var res = 0

    while(lt<=rt) {
        mid = (lt+rt)/2
        if(Count(mid) >= N) {
            res = mid
            lt = mid + 1
        } else {
            rt = mid - 1
        }
    }
    println(res)
}

fun Count(mid : Int) : Int {
    var count = 0
    for(i in lines) {
        count += (i/mid)
    }
    return count
}

- 이분탐색 방법이 적용되기 때문에 (lt, rt, mid) 값이 필요하다.

- 처음 범위는 1 ~ 입력받은 값들 중 최대값 (cm) 으로 잡는다. (lt = 1 / rt = lines에서 최댓값 = largest)

- lt 값이 rt 보다 작거나 같을 동안만 while문을 반복한다.

- 이때 mid 값은 lt와 rt를 더하고 2로 나눈 값이다.

- 이 mid 값을 가지고 Count 함수에서 랜선 개수를 구한다.

- 구한 랜선 갯수가 N과 비교했을 때,

   → 크거나 같으면 res에 mid 값을 대입해주고, lt 값을 mid +1 로 바꿔준다.

   → 작다면 rt 값을 mid - 1 로 바꿔준다.

- 최종적으로 res 값을 출력해준다.

 

 

 

** 이분탐색 → 결정 알고리즘에서 사용

 

*** 결정 알고리즘으로 풀 수 있는 문제들의 특징

1. 찾고자 하는 답이 특정 범위 안에 있다는 것을 바로 알 수 있다! (몇 부터 ~ 몇 사이에 답이 있다)

2. 그 범위 안에 답을 정해놓고 → 이분탐색 적용

3. 그 값이 답으로 유효한지 / 유효하지 않은지 확인하는 함수 필요

4. 답이 된다? → 범위를 좁혀서 절반을 날림

(이 과정을 반복하면서 좋은 답을 찾는다.)