240416 [BOJ/백준] 30892. 상어 키우기

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

30892번: 상어 키우기

---

나의 코드

1. 스택으로 풀기(성공)

N, K, T = map(int, input().split())
shark_size = list(map(int, input().split()))
shark_size.sort(reverse=True)  # 가장 작은 상어부터 빈 스택에 넣기 위해 내림차순으로 정렬

stack = []
count = 0

while count < K:  # 먹이를 먹을 수 있을 때까지
    if shark_size and shark_size[-1] < T:  # 먹을 수 있는 상어가 남아있고 그게 현재 상어 크기보다 작을 때
        stack.append(shark_size.pop())  # stack에 먹을 수 있는 상어들을 넣는다.
    else:  
        if stack: # 먹을 수 있는 상어가 남아있을 때
            T = T + stack.pop()  # 제일 큰 상어를 먹는다.
            count += 1           # 먹은 횟수 1 증가

        else:     # 먹을 수 있는 상어가 없을 때 반복문 빠져나감
            break

print(T)

 

2. 백트래킹(시간초과)

def shark(idx, eat_count, T):
    global max_v

    if eat_count > K:
        return

    if idx == N:
        max_v = max(max_v, T)
        return

    if shark_size[idx] < T:
        shark(idx+1, eat_count+1, T+shark_size[idx])
    shark(idx+1, eat_count, T)

shark(0, 0, T)
print(max_v)

결과

---

처음에 백트래킹으로 풀어봤는데 시간초과가 나와서 dp로 풀어봤다. dp는 한번 본 것을 다시 보지 못해 더 작은 상어를 먹지 못한다는 문제가 있었다. 그래서 현조에게 sos를 쳤고 스택으로 푸는 정석이지만 나에게는 신박한 방법을 알 수 있었다. 더 많은 문제를 풀어보면 이런 방법을 생각할 수 있겠지???