[코딩 테스트] 랜선 자르기 (결정 알고리즘) 파이썬

랜선자르기(결정알고리즘)

• 결정 알고리즘을 사용하는 문제에서는 어떠한 수가 특정 값이 있다는것을 가정으로 기준 값을 설정해서 범위를 나눈 뒤 특정 값을 도출하는 과정을 갖는다
• 대표적인 문제인 랜선자르기 문제이다
• K개의 랜선은 길이가 제각각이다. 어떤사람이 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다
• 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다 (이미 자른 랜선은 붙일 수 없다.)
• 편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정한다
• 자를 때는 센티미터 단위로 정수 길이만큼 자른다고 가정한다
• 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오

---

• 아이디어
  • k개의 랜선이 주어졌을때 n개의 랜선을 만들기 위한 최적의 조건을 구하는 문제이다
  • 범위는 주어진 k개의 랜선 중 가장 큰 값을 범위로 설정한다
  • 가장 큰 k값을 중간값으로 설정하고 범위를 조정하면서 특정 값을 도출한다
  • 11개를 만들 수 있는 최대 랜선의 길이를 구하는 문제

k,n =map(int, input().split())
Line= []
res=0

largest=0

for i in range(k):
    tmp = int(input())
    Line.append(tmp)
    largest=max(largest, tmp)

1. 입력 예제에 맞게 값을 받아오는 양식을 만든다
2. max 함수를 사용해서 가장 큰 수를 찾아낸다

입력 예제 :

4 11

802

743

457

539

lt=1
rt=largest

while lt <= rt :
    mid=(lt+rt)//2
    if Count(mid) >= n:
        res = mid
        lt = mid+1
    else:
        rt=mid-1

1. 시작점과 마지막점을 설정해준다
2. 범위는 lt가 rt보다 크면 자동으로 종료된다
3. 중간값을 설정하고 Count 함수를 만들어 값을 넣어준다
4. mid값이 Count 에 들어가서 n보다 크거나 같다는 것은 범위에 해당 한다는 의미로 중간 값을 변경해주고 가능한 큰수를 찾는다
5. 그렇지 않은경우 rt값을 줄여줘서 범위를 찾는다
6. 이 반복문을 계속하다보면 특정한 값이 나온 것 중 최대로 큰 수가 값이다

def Count(len):
    cnt = 0
    for x in Line:
        cnt+=(x//len)
    return cnt

1. 중간 값을 받아와서 len에 넣어준다
2. 만들어 놓았던 List에 있는 값들을 순서대로 불러와서 x에 넣어준 뒤 만들 수 있는 랜선 수를 구해서 cnt에 넣어준다
3. cnt를 반환해준다