BOJ / 1654번 / 랜선 자르기 [Go][Python3]

👩🏻‍💻 문제

1654번: 랜선 자르기

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/1654
// 흔히 parametric search라고도 부르는, 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 테크닉을 배우는 문제
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var k, n int
	fmt.Fscanln(reader, &k, &n)

	var lengths = make([]int, k)
	for i := 0; i < k; i++ {
		fmt.Fscanln(reader, &lengths[i])
	}

	sort.Ints(lengths) // 주어진 랜선 길이중 가장 긴 랜선의 길이를 탐색 범위로 잡기 위해 정렬한다.
	fmt.Fprintln(writer, getMaxLength(n, lengths))
}

func getMaxLength(n int, lengths []int) (maxLength int) {
	start := 1
	end := lengths[len(lengths)-1] // 탐색 범위를 start, end로 지정
	var mid int
	for start <= end {
		mid = (start + end) / 2 // 이분 탐색과 유사한 방식으로 범위를 좁혀 나간다.
		var totalCount int
		for i := 0; i < len(lengths); i++ {
			totalCount += lengths[i] / mid
		}
		if totalCount >= n {
			if maxLength < mid {
				maxLength = mid
				start = mid + 1
			}
		} else if totalCount < n {
			end = mid - 1
		}
	}
	return
}

🎨 Python3

# https://www.acmicpc.net/problem/1654
# 흔히 parametric search라고도 부르는, 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 테크닉을 배우는 문제
import sys

def get_max_length(n, lengths):
    start = 1
    end = lengths[-1]
    mid = 0
    max_length = 0
    while start <= end:
        mid = (start + end) // 2
        total_count = 0
        for i in range(len(lengths)):
            total_count += lengths[i] // mid
        if total_count >= n:
            if max_length < mid:
                max_length = mid
                start = mid + 1
        elif total_count < n:
            end = mid - 1
    return max_length

if __name__ == "__main__":
    k, n = map(int, sys.stdin.readline().split())
    lengths = []
    for i in range(k):
        lengths.append(int(sys.stdin.readline()))
    lengths.sort()
    print(get_max_length(n, lengths))