랜선 자르기

! 하기 전 궁금한 것!

이렇게 숫자를 \n을 기준으로 입력받으면 어떻게 list에 집어넣을까?

k, n = map(int,input().split())
Line=[]
res = 0
for i in range(k):
    tmp = int(input())
    Line.append(tmp)

이렇게 하나하나 읽어야 한다.

문제 hint>>
가장 큰 랜선 길이는 1~802 이다. 이분 검색을 통해 몇개 만들 수 있는지 세고, 많으면 또 중간값을 바꾸고(키우고), 적으면 중간값을 바꾼다(줄인다). 즉 범위를 변경하는 것.

일단 될 수 있는 값(11이상의 줄 개수)이 나오면 res에다 저장하고, 더 큰 길이를 구하기 위해
중간값을 더 좁혀나간다. 유효한 답을 찾아내고 이분검색이 끝날 때 까지 반복한다.

힌트를 보니 풀 수 있었다..

#1. Alt+W+N 입력하고 Alt+W+V :

import sys
sys.stdin = open("input.txt", "rt")


k, n = map(int,input().split())
Line=[]
for i in range(k):
    tmp = int(input())
    Line.append(tmp)

lt = 0
rt = max(Line)
res = 0
while lt<=rt:
    cnt = 0
    for i in range(k):
        mid = (lt+rt)//2
        cnt += Line[i]//mid
    if cnt < n:
        rt = mid-1
    else:
        if res < mid:
            res = mid
            lt = mid+1
print(res)

결과는 100점이다

선생님 코드

#1. Alt+W+N 입력하고 Alt+W+V :

import sys
sys.stdin = open("input.txt", "rt")

def Count(len):
    cnt =0
    for x in Line:
        cnt+= (x//len) #len의 길이를 갖는 cnt개의 랜선 수 리턴
    return cnt

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)

lt = 0
rt = largest

while lt<=rt:
    mid = (lt+rt)//2
    if Count(mid) >= n: #count 함수를 만든다.
        res = mid
        lt = mid +1
    else:
        rt=mid-1
print(res)

가끔은 함수의 활용이 더 깔끔해 보인다..

반례 수정 !!

만약 입력이

9일 경우에 이 답이 1로 나온다. 논리에 문제가 있다.
dvd가 갯수 만큼 있어어서 하나씩 넣을 수 있다해도, 용량제한이 필요하다..

#1. Alt+W+N 입력하고 Alt+W+V :

import sys
sys.stdin = open("input.txt", "rt")

def Count(capacity):
    cnt=1
    sum=0
    for x in Music:
        if sum + x > capacity:
            cnt+=1
            sum=x
        else:
            sum+=x
    return cnt


n, m = map(int,input().split())
Music = list(map(int,input().split()))
maxx = max(Music)
lt = 1
rt = sum(Music)

res = 2147000000

while (lt<=rt):
    mid = (lt+rt)//2
    if mid>=maxx and Count(mid) <= m: #조건을 하나 더 넣어준다. mid가 maxx보단 크거나 같다고..노래중 가장 긴 노래보다는 용량이 크거나 같다는 이야기다.
        res = mid
        rt = mid-1
    else:
        lt = mid+1
print(res)