[BOJ#30892] 상어 키우기

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

30892번: 상어 키우기

---

많은 시행착오가 있었다..

제출 코드

N, K, T = map(int, input().split())
shark = list(map(int, input().split()))
shark.sort(reverse=True)

cnt = 0
st = []
feed = T
while cnt < K:
    
    if shark and shark[-1] < T: # 샤크에서 T보다 작은 애들을 꺼내서 순서대로저장
        st.append(shark.pop()) # 스택에 추가
    else:
        if st:
            feed = st.pop() # 꺼내서 저장
        else:
            print(T)
            exit()
       
        T += feed
        cnt += 1

print(T)

 

먹이가 될 상어들을 내림차순으로 받아두고, 먹는 횟수만큼 순회를 한다고 정의한다.

먹이가 될 상어가 있고, 마지막에 있는 상어가(내림차순이라 제일 작은상어다) 샼보다 작다면

pop으로 새로운 st 리스트에 차례로 저장한다. - 이 경우 먹지는 않아서 cnt 가 늘어나진 않음

 

먹이가 될 상어가 없거나, 상어 리스트에 마지막에 들어온 상어가 샼보다 크다면 else 문으로 들어가서

조건문을 지나고 먹은 횟수를 추가해주고 샼의 크기를 키워준다.

 

샼의 크기가 갱신되기 때문에 while 문을 돌 때마다 커진 샼을 기준으로 조건문을 실행할 수 있고,

결과적으로 상어 리스트를 한번 순회하는 것이기 때문에 시간 복잡도에서도 자유로워질 수 있었다.