문제 바로가기
문제:
정래는 김밥가게 “그르다 김가놈”에 납품할 김밥을 만드는 김밥 공장을 운영한다. 정래는 김밥 양쪽 끝을 “꼬다리”라고 부른다. 그리고 꼬다리를 잘라낸 김밥을 “손질된 김밥”이라고 부른다. 공장에서는 김밥 N개에 대해서, 김밥 꼬다리를 잘라내고 손질된 김밥을 김밥조각으로 만드는 작업을 한다. 꼬다리를 잘라낼 때에는 양쪽에서 균일하게 K cm만큼 잘라낸다. 만약 김밥의 길이가 2K cm보다 짧아서 한쪽밖에 자르지 못한다면, 한쪽만 꼬다리를 잘라낸다. 김밥 길이가 K cm이거나 그보다 짧으면 그 김밥은 폐기한다. 손질된 김밥들은 모두 일정한 길이 P로 잘라서 P cm의 김밥조각들로 만든다. P는 양의 정수여야 한다. 정래는 일정한 길이 P cm로 자른 김밥조각을 최소 M개 만들고 싶다. P를 최대한 길게 하고 싶을 때, P는 얼마로 설정해야 하는지 구하시오.
입력:
첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. (1 ≤ L ≤ 109, L은 정수)
출력:
김밥조각의 길이 P를 최대로 할 때, P를 출력한다. 만족하는 P가 없는 경우, -1을 출력한다.
풀이:
import sys
sys.stdin = open('/Python/h.txt', 'r')
N, K, M = map(int,sys.stdin.readline().rstrip().split(" "))
# 김밥 손질
arr = []
for _ in range(N):
kim = int(input().rstrip())
#꼬다리 * 2 보다 크면 자를 수 있 손질된 김밥 길이 arr에 저장
if kim > K*2:
arr.append(kim-(2*K))
# 김밥 길이보다 길거나 1개 밖에 안잘릴경우
elif kim - K > 0 and kim < 2 * K:
arr.append(kim-K)
arr.sort()
# 자른게 없음
if len(arr) == 0:
print(-1)
exit()
res = -1
left,right = 1,arr[-1]
while left <= right:
mid = ( left + right ) // 2 # 김밥 최대 길이저장
total = sum([i//mid for i in arr]) # 각 길이마다 몫을 더해줌
if total < M: # 몫이 원하는 M보다 작으면 최댓값이 작아져야함
right = mid-1
else: # 반대 맞는경우도 있으니 res도 최신화
left = mid+1
res = mid
print(res)
처음에는 그리디 알고리즘 인 줄 알았다.
작은 순으로 정렬한후 꼬다리들만 남겨두고 각 꼬다리를 남겨주려고 했는데 아이디어만 생각하고 하지 않았다.
그래서 위에코드처럼 이분탐색을 사용하였다.
우선
# 김밥 손질
arr = []
for _ in range(N):
kim = int(input().rstrip())
#꼬다리 * 2 보다 크면 자를 수 있 손질된 김밥 길이 arr에 저장
if kim > K*2:
arr.append(kim-(2*K))
# 김밥 길이보다 길거나 1개 밖에 안잘릴경우
elif kim - K > 0 and kim < 2 * K:
arr.append(kim-K)
arr.sort()
# 자른게 없음
if len(arr) == 0:
print(-1)
exit()김밥을 문제를 보고 손질해 주었다. 1개 밖에 안 잘리는 경우에도 1개는 집어 넣어줘야한다.
근데 자른게 없으면 0 을 출력하고 종료해야한다.
res = -1
left,right = 1,arr[-1]
while left <= right:
mid = ( left + right ) // 2 # 김밥 최대 길이저장
total = sum([i//mid for i in arr]) # 각 길이마다 몫을 더해줌
if total < M: # 몫이 원하는 M보다 작으면 최댓값이 작아져야함
right = mid-1
else: # 반대 맞는경우도 있으니 res도 최신화
left = mid+1
res = mid
print(res)
그리고 이분탐색을 해주면 된다.
근데 else 부분에서 res = mid로 바궈준다 바꿔준다음에도 또 탐색을 해준다.
댓글