[Baekjoon] 14281. 볼록 수열 - python

https://www.acmicpc.net/problem/14281

14281번: 볼록 수열

문제 정보

문제 유형 난이도 걸린 시간 해결 유무 스스로 구현 성공

백트래킹

실버2

40m

o

x

설계 방법

백트래킹 알고리즘

코드

처음 접근 - 무작정 그리디

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
cnt = 0

for i in range(1, len(arr)-1):
    print(arr)
    if arr[i-1]+arr[i+1] < 2*arr[i]:
        while arr[i-1]+arr[i+1] < 2*arr[i]:
            arr[i] -= 1 
            cnt += 1

print(cnt)

# 이 경우는 뒤의 수가 바뀌었을 때 볼록이 안되게 변할 수 있음

백트래킹으로 접근해야함을 깨달음

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
cnt = 0

def back(n, arr):
    global cnt
    is_convex = True
    for i in range(1, n-1):
        if arr[i-1]+arr[i+1] < 2*arr[i]:
            while arr[i-1]+arr[i+1] < 2*arr[i]:
              arr[i] -= 1 
              cnt += 1
            is_convex = False
    return cnt, is_convex

while True:
    cnt, is_convex = back(n, arr)
    if is_convex: 
        break
  
print(cnt)

바꾸고 끝나는 것이 아니라, arr[i]-=1 했을 때, 앞 쪽 수열이 볼록이 아니게 될 수 있으므로 백트래킹으로 풀어야 했음

근데 시간초과 남

for문안에 while문이 돌면서 시간복잡도가 O(N^2)이 됨

시간초과 해결 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
cnt = 0

def back(n, arr):
    global cnt
    is_convex = True
    for i in range(1, n-1):
        if arr[i-1]+arr[i+1] < 2*arr[i]:
            tmp = arr[i]- (arr[i-1] + arr[i+1])//2
            arr[i] -= tmp
            cnt += tmp
            is_convex = False
    return cnt, is_convex

while True:
    cnt, is_convex = back(n, arr)
    if is_convex: 
        break
  
print(cnt)

while문을 돌지 않고, 1씩 빼야 할 만큼 계산을 해줌

for문안에 있는 while문은 별로 안 돈다고 생각했는데 확실히 연산하는 것 보다는 많이 잡아먹구나

(당연) O(N)이니 ..

참고

https://velog.io/@jieonyoo/백준-14281번-볼록-수열