[백준] 14281번: 볼록 수열

스스로 푼 문제: O
걸린 시간: 55분

문제

풀이

a[i]를 a[i]-1로 바꾸는 연산만 허용된다라는 조건을 a[i]를 a[i-1]로 바꾸는 연산만 허용된다라고 잘못 봐서 40분 정도 헤맸다.

조건을 만족할 때까지 가운데 숫자를 줄이는데 이 과정에서 반복문으로 1씩 빼는 것이 아니라 연산으로 어디까지 줄여야하는지를 계산하도록 한다.

코드

def back_tracking(n, nums):
  global ans
  is_convex = True
  for i in range(1, n-1):
    if nums[i-1] + nums[i+1] < 2 * nums[i]:
      new =  nums[i] - (nums[i-1] + nums[i+1]) // 2
      nums[i] -= new
      ans += new
      is_convex = False
  return ans, is_convex

ans = 0
while True:
  ans, is_convex = back_tracking(n, nums)
  if is_convex:
    break

print(ans)