[Silver II] 태종대 낚시 맛집 - 33847

문제 링크

성능 요약

메모리: 114216 KB, 시간: 1060 ms

분류

구현, 브루트포스 알고리즘, 시뮬레이션

제출 일자

2026년 04월 25일 22:04:59

문제 설명

태종대에는 낚시 맛집이라 불리는 낚시 포인트가 있다. 낚시 맛집에는 서로 다른 크기의 $n$마리의 물고기가 살고 있다. 각 물고기는 먹성, 크기, 가격이 다양해 어떤 물고기가 낚이는 지에 따라 낚시 결과가 결정된다.

산지니는 물고기를 낚기 위해 떡밥을 던져서 물고기를 유인하려 한다. 너무 떡밥을 자주 던지면 물고기가 놀라 도망갈 수 있으므로 최대 한 번 떡밥을 원하는 만큼 던지고자 한다. 산지니가 떡밥을 낚시 맛집에 던지면 아래 과정이 반복되어 물고기가 유인된다.

1. 낚시 포인트에 남은 떡밥의 개수 $t$보다 작거나 같은 먹성의 물고기 중 가장 크기가 큰 물고기가 유인된다.
2. 유인된 물고기는 자기 먹성 만큼의 떡밥을 먹는다.
3. 산지니는 낚시의 달인이기 때문에 유인된 물고기를 항상 낚을 수 있다. 산지니는 낚은 물고기의 가격만큼의 수익을 얻는다.

산지니는 물고기가 더 이상 유인되지 않거나 원하는 경우 낚시를 종료하고 이익을 계산하러 집으로 간다. 떡밥의 가격과 각 물고기의 먹성, 크기, 판매 가격이 주어질 때 산지니가 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오. 산지니가 얻은 이익은 낚은 물고기의 가격 합에서 사용한 떡밥의 가격을 뺀 값이다.

입력

첫 번째 줄에 물고기의 수를 나타내는 정수 $n$이 주어진다. ($1 \leq n \leq 100$)

두 번째 줄에 떡밥 한 개의 가격 $c$가 주어진다. ($1 \leq c \leq 100$)

세 번째 줄부터 $n$개의 줄에 걸쳐 물고기의 먹성 $x$, 크기 $s$, 가격 $w$이 한 줄에 하나씩 공백으로 구분되어 주어진다. ($1 \leq x \leq 100; 1 \leq s \leq 10\,000; 1 \leq w \leq 10^7$)

모든 물고기의 크기는 서로 다르다. 주어지는 모든 수는 정수이다.

출력

산지니가 얻을 수 있는 최대 이익을 출력한다.

---

💡 해결 방법

💻 코드

n = int(input())#물고기의수
c = int(input())#떡밥한개의 가격
fishes = []
 
for i in range(n):
    #물고기의 먹성 x, 크기 s, 가격 w이
    fish = list(map(int, input().split()))
 
                    
    fishes.append(fish)
 
# 낚시 포인트에 남은 떡밥의 개수 t보다 작거나 같은 먹성의 물고기 중 가장 크기가 큰 물고기가 유인된다.
# 유인된 물고기는 자기 먹성 만큼의 떡밥을 먹는다.
 
#최대 떡밥은 100 * 100
 
 
ans = 0
 
for now in range(0, 100*100 + 1):
    nowfeed = now
    nowfishes = [x for x in fishes]
    nowans = -( now * c)
 
    #now가 던지는 떡밥
    while any(x[0] <= nowfeed for x in nowfishes ):#남아있는 물고기들중에 유효한 물고기가 있는한 반복
 
        cangetfishes = [x for x in enumerate(nowfishes) if x[1][0] <= nowfeed]#남은 물고기들중에서 떡밥에 관심있는애들만
        
        getedfish = max(cangetfishes, key = lambda x : x[1][1])#그중에 최대 크기
        nowfeed -= getedfish[1][0]#떡밥을 뺴고
        nowans += getedfish[1][2]#가격을 더하고
        nowfishes.pop(getedfish[0])#nowfishes의 인덱스를 참조하여, 잡은 물고기는 제거한다
 
    ans = max(ans, nowans)
 
 
print(ans)