[알고리즘] 떡볶이 떡 만들기

예전에는 어려웠던 문제를 쉽게 풀 수 있게 되어 뿌듯함에 기록을 남긴다. 아직은 갈길이 멀지만 예전의 나와 비교하면 훨씬~ 실력이 늘었다.
돌이켜 보니 이런 점들이 달라졌다.

1. 항상 먼저 생각한 뒤 코드를 작성한다.
2. 생각한 풀이과정을 주석으로 꼼꼼히 작성한다.
3. 만약 풀이과정이 틀렸을 경우 pop()하면서 역순으로 디버깅한다.
4. 입력크기를 분석해서 사용가능한 시간복잡도를 선택한다.
5. 메서드를 사용하기 전에 해당 메서드의 시간복잡도를 고려한다.

실력이 오르니 문제를 잘 맞춰서 재밌고, 자아효용감이 향상되서 더 어려운 문제도 도전해보고 싶은 욕구가 생긴다. 앞으로 개발자로서 성공적인 커리어를 이어가고 hop by hop으로 이직하려면 항상 숙지하고 있어야할 내용들이라 생각한다. 게다가 지적으로 흥미롭기까지 하니 감히 열심히 공부하지 아니할 수가 있겠는가

# 입력 및 기본 변수 처리
count, length = map(int, input().split())
lines = list(map(int, input().split()))

max_line = max(lines)

'''
아이디에이션
이진탐색의 시작점은 1인데, 1만큼 잘랐을 경우 왠만하면 가능할거거든
일단 처음에 sum을 구한다.
start부터 end의 범위까지 정렬되어 있으므로 이진탐색한다.
탐색의 종료조건은 어떻게 되는가?
'''

answer = 0 # 최악의 경우 0으로 잘라야 할 수도 있음.
start = 0
end = max_line - 1
while start <= end:
    # mid가 자르는 길이다.
    mid = (start + end) // 2
    # mid로 잘랐을때 0이거나 0보다 작은 line은 토탈 계산에서 제외해야한다.
    new_total = sum([line - mid for line in lines if line - mid > 0])
    print(mid, new_total)
    # 만약 잘라낸 후의 길이가 손님이 원하는 길이가 아니면 더 적게 자르는쪽으로 탐색
    if new_total < length:
        end = mid - 1
    # 만약 손님이 원하는 길이 이상으로 자르는 것을 성공했으면
    # 최적화를 위해 더 많이 잘라도 되는지 탐색해봐야 한다.
    else:
        answer = mid
        start = mid + 1
print(answer)