백준 2805번 바로가기

첫 번째 풀이

# 입력
n, m = map(int,input().split())
tree = list(map(int,input().split()))
h = max(tree)
current = 0

# 함수
def relu(x):
  if x>0:
    return x
  else:
    return 0

# 처리
while current < m:
  temp = 0
  for t in tree:
    temp += relu(t-h)
  current = temp
  h -= 1

print(h+1)

두 번째 풀이

# 입력
n, m = map(int,input().split())
tree = list(map(int,input().split()))
start,end = 1,sum(tree)

# 함수
def relu(x):
  if x>0:
    return x
  else:
    return 0

# 처리
while start <= end:
  mid = (start + end) // 2
  temp = 0
  for t in tree:
    temp += relu(t-mid)
  if temp >= m:
    start = mid + 1
  else:
    end = mid-1

print(end)

CODE REVIEW

  1. 첫 번쨰 풀이에서는 브루트포스로 h를 max(tree)에서 1씩 내려가며 확인하는 방식을 취했다. 시간초과 에러로 탈락… 이분탐색 알고리즘을 활용해보자.
  2. 두 번째 풀이에서는 이분탐색을 활용해서 해결했다. h의 범위를 start,end로 잡고 start=end될 때 까지 반복했다.
  3. 자른 나무의 길이를 어떻게 구현할까 고민하다가, 머신러닝에서 activation function 중 하나인 relu를 가지고 구현했다.
    • 근데 메모리 아끼기 위해서는 relu()함수 대신 if t>h: temp+=t-mid로 구현하는게 나을 것 같긴 하다.