[김태원 알고리즘] 랜선자르기 (결정 알고리즘)

사용 언어: Python3

문제

풀이

내 풀이

K, N = map(int, input().split())
lst = [int(input()) for _ in range(K)]
lst.sort()

src, dest = 1, lst[-1]
mid = 0
while src<=dest:
    mid = (src+dest)//2
    cnt = 0
    for x in lst:
        cnt += x//mid
    if cnt == N:
        break
    elif cnt > N:
        src = mid + 1
    else:
        dest = mid - 1
print(mid)

• 예제 입출력은 만족하지만, 처음 dest를 1000으로 설정했을 때에는 200이 나오지 않는다…

다른 풀이

K, N = map(int, input().split())
lst = [int(input()) for _ in range(K)]

src, dest = 1, max(lst)
mid = 0
res = []
while src<=dest:
    mid = (src+dest)//2 # 자른 랜선의 길이
    cnt = 0
    for x in lst:
        cnt += x//mid
    if cnt >= N:
        res.append(mid) # ✅ N개보다 많이 만들어지는 경우까지 모두 res에 저장
    if cnt >= N: # ✅ 등호 위치 주의 (아래 else문이 아니라 여기)
        src = mid + 1
    else:
        dest = mid - 1
print(max(res))

• 정답!
• N개보다 많이 만들어지는 경우까지 모두 res에 저장한 뒤, res의 max 값을 출력하는게 핵심

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기