떡볶이 떡 만들기

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

문제 요약:

숫자 배열이 주어지고 특정 수보다 큰 수들과의 차이의 합이 정해진 m보다 커지는 수중 가장 큰수를 구하여라

실버2

 

소요시간:

~

 

1차 접근 :

먼저 m의 범위를 보고 2진탐색을 해야겠다고 생각한 뒤,  중간값을 정하고 이진탐색을 진행했다.

from bisect import bisect_left
import sys
input = sys.stdin.readline

n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()

s = 0 
e = arr[-1]

while s<e:
	m = (s+e)//2
	idx = bisect_left(arr,m)
	
	new = 0
	for i in range(idx,len(arr)):
		new += arr[i]-m
	#print(s,m,e,new)
	if new==k :
		print(m)
		break
	if new >k :
		s = m+1
	if new <k :
		e = m-1

else:
	print(m-1)

실패 했으며, 작성하면서도 근사치 까지 갔을때 무엇이 최소값이 되는지 정하는것이 잘 안 됐다.

 

답 확인:

from bisect import bisect_left
import sys
input = sys.stdin.readline

n,k = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()

s = 0 
e = arr[-1]

while s<=e: #바뀐부분
	m = (s+e)//2
	idx = bisect_left(arr,m)
	
	new = 0
	for i in range(idx,len(arr)):
		new += arr[i]-m

	if new <k : #왼쪽탐색
		e = m-1
	else:		#오른쪽탐색
		result = m #최대한 덜 잘랐을때가 정답
		s = m+1

print(result)

오른쪽 탐색할 때 그 m값이 최대한 덜잘랐을 때 이므로 그 때 최신화를 해준다.