길이가 제각각인 K개의 랜선이 있다.
이 K개의 랜선들을 잘라서 N개의 같은 길이의 랜선으로 만들고자 한다.
예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다)
랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정
자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정
N개보다 많이 만드는 것도 N개를 만드는 것에 포함
이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성
첫째 줄에는 엘리트학원이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력됨
그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 이하의 자연수로 주어진다.
N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력
입력예시)
4 11
802
743
457
539
출력예시)
200
내가 쓴 코드
#첫번째 코드: 테스트케이스5개 중 4개 통과, 1개 시간초과 ㅜ
#랜선들, 자를 길이 넣으면 총 몇개로 잘렸는 지 나오는 함수 정의
def numOfCuts(lst, cutLength):
cnt = 0
for x in lst:
cnt += x//cutLength
return cnt
#입력 받기
N, K = map(int, input().split())
lst = []
for _ in range(N):
lst.append(int(input()))
totLength = sum(lst)
avgCutLength = int(totLength/K)
cutLength = avgCutLength
#평균 자를 길이로 k 구해 보고 길이 늘릴 지 줄일 지 결정
#평균으로 자른 갯수가 k보다 크거나 같을 경우, k개 이상 유지 하면서 길이 1씩 늘리기
if numOfCuts(lst,cutLength) >= K:
while(numOfCuts(lst,cutLength) >= K):
cutLength += 1
cutLength-=1
print(cutLength)
#평균으로 자른 갯수가 k보다 작은 경우, K보다 같거나 클 때까지 길이 1씩 줄이기
else:
while True:
cutLength -= 1
if (numOfCuts(lst,cutLength) >= K):
print(cutLength)
break
내가 쓴 코드2
#두번째 코드
import sys
sys.stdin = open("input.txt", 'rt')
#랜선들, 자를 길이 넣으면 총 몇개로 잘렸는 지 나오는 함수 정의
def numOfCuts(lst, cutLength):
cnt = 0
for x in lst:
cnt += x//cutLength
return cnt
#입력 받기
N, K = map(int, input().split())
lst = []
for _ in range(N):
lst.append(int(input()))
#이진검색으로 최적의 길이 찾기!
lt = 1
rt = max(lst)
result = 0
while lt <= rt:
mid = (lt + rt) // 2
# 평균으로 잘랐을 때 k개 이상이면 길이 늘리기
if numOfCuts(lst, mid) >= K:
result = mid
lt = mid + 1
# 평균으로 잘랐을 때 k개 미만이면 길이 줄이기
else:
rt = mid - 1
print(result)
모범답안
#모범답안
import sys
sys.stdin=open("input.txt", "r")
def Count(len):
cnt=0
for x in Line:
cnt+=(x//len)
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=1
rt=largest
while lt<=rt:
mid=(lt+rt)//2
if Count(mid)>=n:
res=mid
lt=mid+1
else:
rt=mid-1
print(res)느낀점
1. 아니 문제에서 모든 랜선의 길이를 같게 하고 싶다며... 그래서 당연히
동일하게 할 길이가 애초에 가지고있던 모든 랜선들보다는 작아야되는줄. 그게 맞는거아님?
다 동일하게 하고 싶다매.... 암튼
2. 첫번째 코드는 올바른 답을 도출해내는것 같긴하지만.. 마지막 테스트케이스에서
시간 초과가 떠버렸당. 평균에서 시작해서 하나씩 늘리고 줄여나가는게 너무 오래걸리려나
하나씩 늘리고 줄이는 방법이 아닌 이진검색과 같은 방식으로 늘리고 줄이자.
3. 이진검색 할 때 포인터와 같은 lt rt만들고 이동하는 방법은 그냥 외우자
중요한 점은 양극단, 특히 최대값을 무엇으로 설정할 지 인듯하다.
4. 모범답안과 거의 동일!!하게 풀었다 야호 근데 난 내 코드가 더 맘에 든당.ㅎ
5. **찾고자 하는 답이 특정 범위 안에있고, 그 안에 있는 숫자를 결정할때, 이분검색을 사용
(결정 알고리즘)**
