비슷한 백준 문제 https://www.acmicpc.net/problem/2805

문제에서 요구하는 것은 위 백준 문제와 똑같다. 단순히 떡볶이에서 나무로 바뀐것이다.

접근

1차

일단 문제를 보고 이진 탐색을 통해서 최대로 자를 수 있는 길이를 찾아야겠다고 생각했다. 그래서 떡볶이 길이 배열을 이진 탐색을 통해서 중간점을 찾는 방식으로 구현하였지만 생각해보니까 배열에 없는 숫자가 답일 수 있다. 따라서 이 접근은 틀렸다는 것을 깨달았다.

2차

이진 탐색을 통해서 최대 최소 값을 건내주고 그 둘의 평균을 mid 로 하여 target 과 같은지 탐색하는 방법으로 구현했다. 그러긴 위해서 mid 를 건내주면 나머지 떡의 길이의 합을 구하는 함수를 따로 구현했는데 이 함수의 복잡도가 O(N) 이고 이진 탐색이 O(logN) 으로 어느정도 괜찮겠다 싶었다.

def sum_left(array, length):
	result = 0
	for i in array:
		left = i - length
		if left <= 0:
			continue
		result += left
	return result

def binary_search(array, target, min, max):
	while min <= max:
		mid = (min + max) // 2
		tmp = sum_left(array, mid)
		if tmp == target:
			return mid
		elif tmp > target:
			max = mid - 1
		else:
			min = mid + 1
	return -1

그러나 이 코드도 어딘가 문제가 있었다.. 이틀동안 고민하고 풀어봤는데 시간만 있으면 풀 수 있을 것 같으나 더이상 시간을 소비할 수 없어서 일단 답을 보고 배우자는 생각을 하게 되었다.

해설

전체적인 흐름은 내가 시도 했던 방법과 비슷했다. 하지만 위의 코드와 해설과 다른 부분은 바로 조건 부분이였다. 나는 위 코드에서 tmp 가 target 과 같아지는 경우와 아닌 경우를 나눠야 하고 그에 대한 처리를 따로 해줘야 하는게 이부분에서 계속 뭔가 잘 안풀렸다. 그런데 해설을 보니까 그냥 단순히 tmp < m 인 경우에는 max = mid - 1 로 해주고 아닌 경우에는 일단 답이 될 수 있으니까 result 라는 변수에 mid 를 저장해두고 start = mid + 1 로 해주어 다시 반복문을 도는 방식이였다. 이렇게 구현하면 다시 조건에 충족 되는 경우에는 result 가 업데이트 되고 업데이트 되는 result 는 기존에 result 의 값보다는 큰 값이 들어오게 된다.

import sys

def solution():
	n , m = list(map(int, input().split()))
	array = list(map(int, sys.stdin.readline().rstrip().split()))


	start = 0
	end = max(array)

	result = 0
	while start <= end:
		mid = (start + end) // 2
		total = 0
		for i in array:
			if i > mid:
				total += i - mid
		if total < m: # 떡이 부족한 경우
			end = mid - 1
		else: 
			result = mid
			start = mid + 1

	print(result)
solution()

참고로 이렇게 solution 이라고 따로 함수를 만들어서 실행시키는 방식으로 하면 함수 없이 그냥 코드를 작성하는 것보다 더 빠르게 처리가 된다. 그 이유는 만약에 함수안에 구현을 해두면 변수들이 local 변수로 선언되는 반면 함수 없이 구현하면 global 로 선언되는 것이기 때문에 유의미한 속도 차이가 발생한다고 한다. (출처 : https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function)