[이코테] 이진 탐색_떡볶이 떡 만들기 (python)

juyeon·2022년 7월 5일
0

나의 풀이

1. 오류남 ㅠ

n, m = map(int, input().split())
rice = sorted(list(map(int, input().split()))) #정렬된 리스트

#이진 탐색(재귀 함수 이용)
def sell(arr, target, start, end):
    #최소한 m만큼 떡을 잘라야 하므로,
	#즉 최대한 덜 잘라냈을 때가 정답
    if start > end:
		return mid
        
	amount = 0 #잘라낸 떡의 양
    mid = (start + end) // 2 #중간점 
    
    for i in arr: #떡 리스트를 보면서
		#중간점 이상의 떡을 잘라내어서 잘라낸 떡의 양 증가
        if mid < i: 
            amount += i - mid 
            
	#더 적게 잘라냈을 때, 더 잘라내기(재귀 함수)
    if amount < target:
        return sell(arr, target, start, mid - 1)
    
	#더 많이 잘라냈을 때, 덜 잘라내기(재귀 함수)
    else:
        return sell(arr, target, mid + 1, end)
        
print(sell(rice, m, 0, max(rice)))
  • invalid syntax (<string> local variable 'mid' referenced before assignment) 오류 발생!
    : 전역 변수를 지역 변수로 호출해서 발생하는 오류라는데..
    왜...? 난 멀쩡하게 코드 썼는데..?
    ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

2. global 변수 추가 & 종료 조건 변경

n, m = map(int, input().split())
rice = sorted(list(map(int, input().split()))) #정렬된 리스트

#이진 탐색(재귀 함수 이용)
def sell(arr, target, start, end):
	#'mid' 변수 오류가 나서, 전역 변수 선언.
    #그러나.. 왜 이게 오류가 난지는 모르겠음 ㅠㅠ
	global mid
    
    #최소한 m만큼 떡을 잘라야 하므로,
	#즉 최대한 덜 잘라냈을 때가 정답
    if start == end:
		return mid
        
	amount = 0 #잘라낸 떡의 양
    mid = (start + end) // 2 #중간점 
    
    for i in arr: #떡 리스트를 보면서
		#중간점 이상의 떡을 잘라내어서 잘라낸 떡의 양 증가
        if mid < i: 
            amount += i - mid 
            
	#더 적게 잘라냈을 때, 더 잘라내기(재귀 함수)
    if amount < target:
        return sell(arr, target, start, mid - 1)
    
	#더 많이 잘라냈을 때, 덜 잘라내기(재귀 함수)
    else:
        return sell(arr, target, mid + 1, end)
        
print(sell(rice, m, 0, max(rice)))
  • global mid: 추가하니까 정상 작동 됨. 왜...지...?
    도대체, 왜!!!!!! 이걸 추가 해야 하는건데!!!!!!
  • if start == end로 변경: if start < end으로 했을 때 결과값이 1 더 크게 나옴.. 그래서 부랴부랴 바꾸긴 했는데, 맞는지는 잘...
profile
내 인생의 주연

0개의 댓글