사용자 도구

사이트 도구


ps:problems:boj:1654

랜선 자르기

ps
링크acmicpc.net/…
출처BOJ
문제 번호1654
문제명랜선 자르기
레벨실버 3
분류

파라메트릭 서치

시간복잡도O(nlogm)
인풋사이즈n<=10,000, m<=2^31
사용한 언어Python
제출기록34484KB / 124ms
최고기록72ms
해결날짜2021/07/13
태그

21단계

풀이

  • 파라메트릭 서치로 풀 수 있는 문제
  • 길이가 l인 랜선을 최대 몇개 만들수 있는지는, 간단하게 각 랜선을 l로 나눈 몫의 합으로 구할수 있다. 만들수 있는 랜선의 갯수가 N이상이 되는 l의 최댓값을 이분 탐색으로 찾으면 된다.
  • 결정 문제를 푸는 데에는 O(K)이 걸린다 (K=랜선의 갯수). 이분탐색의 탐색 범위는 단순하게는 0부터 가장 긴 랜선의 길이까지로 처리해도 충분하다. 조금 더 복잡하게 하면 {전체 랜선의 길이 / 필요한 랜선의 갯수} 로 처리하면 구간의 범위가 O(m)에서 O(m*K/N)로 조금 더 작아지긴 하지만 (m=랜선의 최대 길이, N=필요한 랜선의 개수), 실행시간에는 큰 차이는 없다. 전체 시간복잡도는 O(K*logm) 또는 O(K*log(m*K/N))이 된다.

코드

"""Solution code for "BOJ 1654. 랜선 자르기".

- Problem link: https://www.acmicpc.net/problem/1654
- Solution link: http://www.teferi.net/ps/problems/boj/1654
"""

import sys
from teflib import binsearch


def main():
    K, N = [int(x) for x in sys.stdin.readline().split()]
    lengths = [int(sys.stdin.readline()) for _ in range(K)]

    answer = binsearch.maximum_valid_integer(
        1,
        max(lengths) + 2,
        lambda target_len: sum(l // target_len for l in lengths) >= N)

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
G Y K E T
 
ps/problems/boj/1654.txt · 마지막으로 수정됨: 2022/04/22 13:43 저자 teferi