백준 1654번 랜선 자르기 파이썬 풀이(feat. 메모리 초과 해결)

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

---

정답코드

# 랜선 자르기
import sys

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

def Binary(target, start, end):
    # 탈출 조건
    if start > end:
        print(end)
        return

    mid = (start + end) // 2
    
    line = 0
    for i in lines_list: #입력값 리스트 원소 하나씩 비교해서 넣어주기
        tmp = i // mid
        line += tmp
        
    if line < target: # 값이 작으면 나누는 수가 작아져야 하므로
        return Binary(target, start, mid-1) # 왼쪽
    else:
        return Binary(target, mid+1, end) # 오른쪽

Binary(N, 1, max(lines_list))

Q) 탈출조건 저렇게 해도되는건가요?

4 11

899

799

499

539

입력의 예를 들어 탈출 조건을 이해해보겠습니다.

이분 탐색과정은 아래와 같이 진행됩니다. 답은 224입니다. 그렇다면 224만 11이라는 값이 도출되는 것인가요?

정답은 아닙니다.

197부터 224까지 모두 11이라는 값이 도출되고 그 중 최댓값이 224인 것입니다. 이는 아래와 같이 동작하면서 구해집니다. 똑같이 이분 탐색을 쭉 활용합니다. ( 값들이 모두 오름차순이거나 내림차순일 경우에만 성립하는 조건)

 

 

풀이과정

1. 틀린풀이

# 랜선 자르기
import sys

K, N = map(int,input().split())
lines_list = []
for i in range(K):
    lines_list.append(int(input()))

compare_list = [x for x in range(1, max(lines_list) + 1)]


def Binary(array, target, start, end):
    
    mid = (start + end) // 2
    
    line = 0
    for i in lines_list: #입력값 리스트 원소 하나씩 비교해서 넣어주기
        tmp = i // array[mid] #마지막으로 나누기
        line += tmp

    # 탈출 조건
    if line == N:
        line2 = 0 #다음거까지 더블 체크
        for i in lines_list: #입력값 리스트 원소 하나씩 비교해서 넣어주기
            tmp2 = i // array[mid+1] #다음꺼 체크해보기
            line2 += tmp2
        if line2 != N: # 더 큰 값 중에 답이 없는 경우만
            print(array[mid])
            return
   
    if line < target: # 값이 작으면 나누는 수가 작아져야 하므로
        return Binary(array, target, start, mid-1) # 왼쪽
    else:
        return Binary(array, target, mid+1, end) # 오른쪽


Binary(compare_list, N, 0, len(compare_list) -1)

 틀린점 

1. 탈줄조건

# 탈출 조건
    if line == N:
        line2 = 0 #다음거까지 더블 체크
        for i in lines_list: #입력값 리스트 원소 하나씩 비교해서 넣어주기
            tmp2 = i // array[mid+1] #다음꺼 체크해보기
            line2 += tmp2
        if line2 != N: # 더 큰 값 중에 답이 없는 경우만
            print(array[mid])
            return

 다음 거만 체크하는 경우인데, 다다음 것이 있을 수 있다.

예를들어 11 11 11 12 이런식의 결과값이 도출되는 경우

두 번째꺼까지만 체크하고 종료해버리므로 최대값을 체크하지 못한다. 따라서 논리적 결함이 있다.

 

2. 배열의 활용(메모리초과)

compare_list = [x for x in range(1, max(lines_list) + 1)]

 배열을 사용하여 메모리 초과가 났다.

 이유: 랜선의 길이가 2^32 -1 이라고 하였다. 

 

배운점 && 공부방향

1. 단순하게 풀면 쉬운문제지만, 하나하나 생각하면서 풀면 어려운 문제였다고 생각한다..

-> 이분 탐색 및 parametric search 는 탈출 조건을 잘 고려하자.