백준 21279번 광부 호석 - Python

 

문제

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

 

 

시도했지만 실패한 방법

• BFS(?) 방법으로 mines[x][y] = mines[x-1][y] + mines[x][y-1] - mines[x-1][y-1] + mineral[x][y] -> O(W*H)로 실패
• 모든 포인트를 반복해서 넣어서 처리 -> O(N^2)로 실패

 

마지막은 투포인터 + set을 활용했다.

 

import sys
from collections import defaultdict
input = sys.stdin.readline
n, cash = map(int, input().split())

x_gems = defaultdict(list) # x좌표에 있는 보석들
y_gems = defaultdict(list) # y좌표에 있는 보석들

for _ in range(n):
    x, y, v = map(int, input().split())
    x_gems[x].append((y, v))
    y_gems[y].append((x, v))


result = 0
cost = 0 # 보석 채굴 비용 = 보석 갯수
value = 0
x = 100_000 # x좌표 최대값
y = 0 # y좌표 최소값


bag = set()

while x >= 0 and y <= 100_000:
    if cost <= cash: # 가방에 더 넣을수 있는 경우
        for _x, v in y_gems[y]:
            if _x <= x:
                bag.add((_x, y))
                cost += 1
                value += v
        y += 1
    else:
        for _y, v in x_gems[x]:
            if (x, _y) in bag: # 이미 가방에 있는 보석이라면
                bag.remove((x, _y))
                cost -= 1
                value -= v
        x -= 1

    if cost <= cash: # 파산하지 않는 경우
        result = max(result, value)

print(result)

 

 

 

 

투 포인터로만 사용해서 구현했을 때는 y값을 기준으로 보석들을 빼내었는데,  이전에 빼낸 보석들의 y 좌표들을 관리해서 더이상 그 y좌표 이상 값들은 선택하지 않도록 제어하는 부분이 어려워 set() 구조를 활요해서 가방에 있는 경우만 빼도록 수정하였다.

 

# 이전
for _y, v in x_gems[x]:
    if _y <= y:
        cost -= 1
        value -= v


# 이후
for _y, v in x_gems[x]:
    if (x, _y) in bag: # 이미 가방에 있는 보석이라면
        bag.remove((x, _y))
        cost -= 1
        value -= v