[PS] BOJ 34955 / 낚시 (Hard)
![[PS] BOJ 34955 / 낚시 (Hard)](/content/images/size/w2000/2026/01/-------------3.png)
문제 링크: https://www.acmicpc.net/problem/34955
풀이
같은 내용에 출력 양식이 다른 문제 (낚시 (Easy))도 존재합니다. 풀이 또한 동일하니, 이 글에서는 Hard 버전의 풀이를 작성합니다.
낚시 조건 살펴보기
처음에 $N$개의 미끼와 $M$마리의 물고기가 있습니다.
문제에서, 우리는 미끼를 사용해 낚시를 하거나 기존에 잡은 물고기를 미끼로 바꾸는 2가지 행동을 할 수 있습니다. 2가지 행동을 적절히 수행해, 잡은 물고기의 가치의 합을 최대로 만들어야 합니다.
물고기를 낚기 위해선 1개 이상의 미끼를 소모해야 합니다. 이 때, 사용한 미끼의 가치의 총합보다 큰 가치를 가지는 물고기를 낚을 수 있습니다. 해당하는 물고기가 여러 마리라면, 그 중 가치가 가장 작은 물고기를 낚습니다. 반대로, 미끼의 가치의 총합이 물고기의 가치보다 크다면 낚을 수 없습니다.
이전에 잡은 물고기를 미끼로 바꿀 때는, 그 물고기와 동일한 가치를 가지는 미끼를 얻고 물고기는 사라집니다.
풀이 생각해보기
예제 데이터에서는 미끼를 2개 이상 사용해 낚시를 하지만, 조건을 잘 생각해보면 미끼를 한 개만 쓰는게 항상 유리합니다. 사용한 미끼의 가치의 총합보다 더 큰 가치를 가지는 물고기만 낚을 수 있으니, 미끼의 가치를 낮춰야 물고기를 낚을 가능성이 올라갑니다. 따라서 항상 한 개의 미끼만 사용하도록 구현했습니다.
같은 이유로, 물고기를 미끼로 바꿀 때는 항상 가치가 낮은 물고기부터 미끼로 바꿨습니다. 최종적으로 잡은 물고기들의 가치의 총합이 높아지려면 가치가 큰 물고기를 가지고 있어야 하고, 가치가 낮은 미끼일수록 물고기를 낚을 가능성이 크기 때문입니다.
구현하기
우선, 미끼와 물고기들의 가치를 오름차순으로 정렬합니다.
이후, 물고기를 기준으로 행동을 결정합니다. 각각의 물고기에 대해, 미끼를 사용해 낚을 수 있다면 낚고 그렇지 않다면 이전에 잡은 물고기를 미끼로 바꿔 낚습니다.
물고기의 가치가 오름차순으로 정렬되어 있으므로, 이전에 잡은 물고기를 미끼로 바꿀 시 항상 다음 물고기를 낚을 수 있습니다.
미끼는 항상 물고기의 가치보다 작은 미끼 중 가장 큰 것을 사용합니다. 미끼는 가치가 작을 수록 잡을 수 있는 물고기의 가치 범위가 넓기 때문에, 되도록 가치가 더 작은 미끼를 아끼는 방향으로 구현했습니다. (자세한 내용은 시행착오 항목에서 설명하겠습니다.)
물고기를 낚을 수 있는 미끼들 중에서 가장 가치가 큰 미끼를 먼저 사용하기 위해, 미끼를 최대 힙으로 관리합니다.
잡은 물고기들은 이후에 물고기를 미끼로 바꾸게 되는 경우를 고려해 최소 힙에 저장합니다.
from heapq import heappush, heappop, heapreplace
baits = sorted(map(int, input().split()))
fishes = sorted(map(int, input().split()))
valid_baits = [] # 사용할 수 있는 미끼를 저장하는 최대 힙.
caught_fishes = [] # 잡은 물고기를 저장하는 최소 힙.
actions = [] # 각 단계에서 진행한 동작의 정보를 저장할 리스트.
bait_idx = 0
for fish in fishes:
while bait_idx < N and baits[bait_idx] < fish:
heappush(valid_baits, -baits[bait_idx])
bait_idx += 1
if valid_baits:
# 사용 가능한 가장 가치가 큰 미끼로 물고기를 낚는다.
bait = heappop(valid_baits)
heappush(caught_fishes, fish)
actions.append((0, -bait))
else:
# 더 이상 사용할 수 있는 미끼가 없다면 물고기를 미끼로 바꾼 뒤 낚는다.
if caught_fishes and caught_fishes[0] < fish:
actions.append((1, caught_fishes[0]))
actions.append((0, caught_fishes[0]))
heapreplace(caught_fishes, fish) # heappop + heappush보다 더 효율적인 방식.전체 코드
from heapq import heappush, heappop, heapreplace
input = open(0).readline
N, M = map(int, input().split())
baits = sorted(map(int, input().split())) # 미끼의 가치를 최소 힙으로 관리한다.
fishes = sorted(map(int, input().split())) # 물고기들의 가치를 최소 힙으로 관리한다.
valid_baits = [] # 사용할 수 있는 미끼를 저장하는 최대 힙.
caught_fishes = [] # 잡은 물고기를 저장하는 최소 힙.
actions = [] # 각 단계에서 진행한 동작의 정보를 저장할 리스트.
bait_idx = 0
for fish in fishes:
while bait_idx < N and baits[bait_idx] < fish:
heappush(valid_baits, -baits[bait_idx])
bait_idx += 1
if valid_baits:
# 사용 가능한 가장 가치가 큰 미끼로 물고기를 낚는다.
bait = heappop(valid_baits)
heappush(caught_fishes, fish)
actions.append((0, -bait))
else:
# 더 이상 사용할 수 있는 미끼가 없다면 물고기를 미끼로 바꾼 뒤 낚는다.
if caught_fishes and caught_fishes[0] < fish:
actions.append((1, caught_fishes[0]))
actions.append((0, caught_fishes[0]))
heapreplace(caught_fishes, fish) # heappop + heappush보다 더 효율적인 방식.
print(len(actions))
for t, x in actions:
if t == 1:
print(f"bait {x}")
else:
print(f"fish {x}")
print(sum(caught_fishes))solution.py
시행착오
처음에는 가치가 작은 미끼와 가치가 작은 물고기를 하나씩 묶어 처리했습니다. 하지만, 이 경우 처리하지 못하는 데이터가 있어 오답을 받습니다.
처음에는 이런 방식으로 코드를 작성했습니다.
from heapq import heappush, heappop
from bisect import bisect_right
N, M = map(int, input().split())
baits = sorted(map(int, input().split())) # 미끼의 가치를 최소 힙으로 관리한다.
fishes = {} # 물고기들의 정보를 {가치: 마리수} 의 형태로 저장한다.
for fish_value in map(int, input().split()):
try:
fishes[fish_value] += 1
except KeyError:
fishes[fish_value] = 1
fish_values = sorted(fishes.keys()) # 이진탐색을 위해 키만 별도로 정렬해서 관리한다.
caught = [] # 최소 힙에 잡은 물고기의 가치를 저장한다.
actions = [] # 매 단계에서 진행한 행동을 기록한다.
def do_fishing():
"""낚시를 진행한다."""
cur_bait = heappop(baits) # 가장 가치가 작은 미끼를 가져온다.
fish_value_idx = bisect_right(fish_values, cur_bait) # 현재 미끼의 가치보다 더 큰 물고기들 중 가치가 가장 작은 물고기의 인덱스를 찾는다.
if fish_value_idx >= len(fish_values): # 해당하는 물고기가 없는 경우
return False # 잡을 수 있는 물고기가 없다.
fish_value = fish_values[fish_value_idx]
if fishes.get(fish_value, 0) > 0: # 물고기를 낚는다.
actions.append(f"fish {cur_bait}")
fishes[fish_value] -= 1
heappush(caught, fish_value) # 잡은 물고기를 최소 힙에 기록
if fishes[fish_value] == 0:
fish_values.pop(fish_value_idx) # 더 이상 잡을 수 있는 물고기가 없다면 목록에서 제거한다.
del fishes[fish_value]
return True
def make_bait():
"""낚은 물고기 중 가치가 가장 작은 물고기 한 마리를 미끼로 바꾼다."""
value = heappop(caught)
heappush(baits, value)
actions.append(f"bait {value}")
while len(fishes) > 0 and len(baits) > 0: # 물고기와 미끼가 남아있는 동안 반복한다.
fishing_res = do_fishing() # 낚시 진행
# 이미 잡은 물고기를 미끼로 바꿀지 결정한다.
# 1. 미끼가 더 이상 없는데 물고기가 여전히 남아있는 경우
# 2. 남은 미끼의 가치가 남은 물고기들의 가치보다 크거나 같은 경우 (조건에 따라 낚시 불가)
# 낚은 물고기들의 가치가 적은것부터 하나씩 미끼로 바꾸고 반복한다.
# 이 때, 미끼로 바꿔서 새 물고기를 낚을 수 있을 때에만 미끼로 바꾼다.
if len(caught) > 0 and len(fishes) > 0 and (len(baits) == 0 or not fishing_res):
if caught[0] < fish_values[0]: # 가지고 있는 물고기를 변환해 더 가치가 큰 물고기를 낚을 수 있을 때에만 미끼로 바꾼다.
make_bait()
# 답 출력하기
print(len(actions)) # Q
if len(actions) > 0:
print("\n".join(actions)) # Q개의 행동
print(sum(caught)) # 잡은 물고기의 가치 합오답 코드
항상 미끼를 한 개만 사용한다는 점은 같으나, 언제나 최소한의 가치를 가지는 미끼를 우선적으로 사용했습니다. 물고기를 미끼로 바꾸는 것 까지 고려해, 물고기와 미끼가 남아있는 동안 계속 반복하며 미끼를 기준으로 낚을 수 있는 물고기를 이진 탐색을 통해 찾았습니다... 복잡하고 느린 방법이었기 때문에, 물고기를 기준으로 다시 작성했습니다.
이전에 가치가 작은 미끼부터 쓰는 방법으로 구현했다가 틀렸었기 때문에, 반대로 사용 가능한 미끼 중에서 가치가 가장 큰 미끼를 먼저 쓰도록 구현했습니다. 하지만, 글을 쓰면서, 가치가 작은 미끼부터 사용해도 결과적으론 동일하다는 점을 깨달았습니다.
가치가 작은 미끼부터 사용하는 풀이로도 문제를 풀었고, 해당 코드도 아래에 첨부합니다.
from heapq import heappush, heappop, heapreplace
from collections import deque
input = open(0).readline
N, M = map(int, input().split())
baits = sorted(map(int, input().split())) # 미끼의 가치를 최소 힙으로 관리한다.
fishes = sorted(map(int, input().split())) # 물고기들의 가치를 최소 힙으로 관리한다.
caught_fishes = []
actions = []
bait_idx = 0
for fish in fishes:
if bait_idx < N and baits[bait_idx] < fish:
# 사용 가능한 가장 가치가 작은 미끼로 물고기를 낚는다.
# 만약, 현재 미끼의 가치가 물고기보다 크다면,
# 이 물고기는 잡았던 물고기를 미끼로 바꿔 낚고 현재 미끼는 보류한다.
heappush(caught_fishes, fish)
actions.append((0, baits[bait_idx]))
bait_idx += 1
else:
# 더 이상 사용할 수 있는 미끼가 없다면 물고기를 미끼로 바꾼 뒤 낚는다.
if caught_fishes and caught_fishes[0] < fish:
actions.append((1, caught_fishes[0]))
actions.append((0, caught_fishes[0]))
heapreplace(caught_fishes, fish) # heappop + heappush보다 더 효율적인 방식.
print(len(actions))
for t, x in actions:
if t == 1:
print(f"bait {x}")
else:
print(f"fish {x}")
print(sum(caught_fishes))가치가 작은 미끼부터 사용하는 풀이