[Python] 백준 #1654- 랜선 자르기

문제

---

 

1654번: 랜선 자르기

코드

---

My answer

import sys
input=sys.stdin.readline

k,n=map(int,input().split())
line=[int(input()) for _ in range(k)]

start,end=0,max(line)+1
while(start<end):
    
    mid=(start+end)//2
    tmp=sum([i//mid for i in line])
    
    if(tmp<n):
        end = mid
    else:
        start = mid + 1
        
print(end-1)

Another answer

import sys
input=sys.stdin.readline

k,n=map(int,input().split())
line=[int(input()) for _ in range(k)]

start,end=1,max(line)
while(start<=end):
    
    mid=(start+end)//2
    tmp=sum([i//mid for i in line])
    
    if(tmp<n):
        end = mid - 1
    else:
        start = mid + 1
        
print(end)

풀이

---

이번 문제도 너무 헷갈렸다...단순한 이진탐색은 짜겠는데 얼마전 정리한 upper bound와 lower bound는 너무 헷갈렸고, 부호 하나 때문에 답이 틀리다보니까 반례도 찾기도 어렵고....우선 반드시 upper bound와 lower bound 개념을 익히고, 코드도 몇번 짜보고 해야한다. 

Algorithm 5. 이진탐색(binary search)

이번 문제의 경우 우선 가장 많이 틀리는 이유가 아래 두개였다. 

1. max값을 랜선값들 중 최대길이가 아니라, 최대길이 +1로 설정해줘야 한다. -> Division error 방지

2. tmp<n일 경우, mid=end이고 최종 출력은 end-1이다. -> Upper bound

1. Division error

 이번 문제의 경우 mid가 자르는 랜선의 길이를 의미하기 때문에 예를 들어 mid=400일경우 802를 400으로 나눠 2조각으로 나뉜다는 개념으로 푸는 문제인데 이때 mid가 0이 되버리면 나눌 수가 없는 division error이 발생한다. 

이를 보여주는 예시를 보자. (end를 max(line)이라고 푼 가정이다.) 랜선이 2개이고, 각각 1,1 이라고할 때, 이 경우에는 start=0이고, end도 1이기 때문에 mid=0이된다. 이러면 mid로 나눌 수가 없게 된다. 따라서 처음에 end를 최대값보다 1을 늘려줘야 한다. 

 

--> 그런데 another answer 에서 처럼 start=1로 잡아주고 조건문에서 start==end일 때도 돌아가게 설정할 경우, end =max(line)으로 잡아도된다. 또한 이럴 경우 end의값도 mid-1로 갱신해줘야한다. 

 

2. Upper bound

이 문제의 경우 N개를 만들 수 있는 랜선의 최대 길이를 찾아야하기 때문에 upper bound로 문제를 해결해야했다.

이게 무슨 말이냐, 예를 들어 문제의 예시와 같이 802, 743, 457, 539가 들어왔을 때 가장 큰 랜선의 길이는 200이지만, 198로 자를 때도 11개, 199cm, 200cm 로 자를 때 또한 모두 11개로 나오게된다. 이 중 우리는 최대값을 찾아야하는데

upper bound= 해당 값보다 큰 값이 처음 나오는 인덱스 반환하는 것(초과)

lower bound= 해당 값 이상의 값이 처음 나오는 인덱스 반환하는 것(이상)

이기 때문에 우리는 upperbound를 이용해서 11을 초과하는 값을 찾은 후 -1을 해주면 됐다. lowerbound로 해주면 가장 맨처음 11개가 나오는 값을 출력하기 때문에 문제가 최소길이를 찾는 것으로 바뀔 것이다. 

https://real-water.tistory.com/57

 

[참고블로그]

[백준] 1654번 : 랜선 자르기 - JAVA [자바]

[백준] 1654 랜선자르기 - Upper Bound/Lower Bound