백준 1202 보석도둑 python

문제 링크  - https://www.acmicpc.net/problem/1202

 

처음엔 배낭알고리즘 문제로 생각했으나 조건에 가방에 들어갈 수 있는 보석의 수는 최대 1개인걸 알고 그리디하게 풀면 되는 문제로 파악했다. (조건 최대 30만개 가방 c의 개수가 최대 1억개 , 제한시간 1초 - > dp활용 배낭알고리즘으로 풀게되면 시간초과 예상)

 

생각

1.보석은 무게 기준으로 정렬, 가방도 크기 기준으로 정렬 , 

2.가방들을 하나씩 순회하며 가방보다 적거나 같은 무게를 가진 보석들 중 가치가 가장 큰 보석 담기

3, 보석의 중복을 막기 위해 가방에 담긴 보석의 가치를 0으로 변경

4.가방의 무게 이하로 포함된다면 무게값은 필요가 없고, 가치가 가장 높은것만 고르면 됨

 

 

최초코드

import sys

import heapq

input= sys.stdin.readline

n,k =map(int,input().split())

#각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

#보석은 무게 Mi와 가격 Vi

jewel = [list(map(int,input().split())) for __ in range(n)]

#가방 중복판매 방지 -> 가방에 담은 보석의 가치 0으로 변경

bags = []

for __  in range(k):

    bags.append(int(input().rstrip()))

jewel.sort()

bags.sort()

print(jewel)

print(bags)

values= [] #가치가 제일 큰 보석만 뽑으면 됨

now = 0

result = 0

for bw in bags:

    for i in range(now,len(jewel)):# 틀리는 부분이 여기일거같은데

        if jewel[i][0]<=bw:

            heapq.heappush(values,-jewel[i][1])

        else:

            break

    now = i #가방 범위 이내의 인덱스 모두 방문해야함

    if values: # 0개일떄 인덱스 오류 발생

        result-=heapq.heappop(values)

print(result)

   

10퍼센트에서 틀림

반례

4 4
1 100
10 500
13 300
2 200
13
13
13
13

-> 인덱스를 변수 now가 문제였다 보석 마지막까지 다 순회하고 보석을 values에 모두 넣었다면 더 이상 for문으로 순회하지 말아야하는데 계속해서 마지막 보석을 values에 넣어줘서 문제가 보석값이 복사가 되었다.

 

import sys
import heapq
input= sys.stdin.readline

n,k =map(int,input().split())

#각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
#보석은 무게 Mi와 가격 Vi
jewel = [list(map(int,input().split())) for __ in range(n)]
#가방 중복판매 방지 -> 가방에 담은 보석의 가치 0으로 변경 
bags = []

for __  in range(k):
    bags.append(int(input().rstrip()))

jewel.sort()
bags.sort()

values= [] #가치가 제일 큰 보석만 뽑으면 됨 

now = 0
flag= 0
result = 0

for bw in bags:
    for i in range(now,len(jewel)):# 틀리는 부분이 여기일거같은데
        if flag: # for문 모두 순회했다면 플래그 설정
            break
        if jewel[i][0]<=bw:
            heapq.heappush(values,-jewel[i][1])
            if i == len(jewel)-1:
                flag=1
        else:
            break
    now = i #가방 범위 이내의 인덱스 모두 방문해야함 
    if values: # 0개일떄 인덱스 오류 발생
        result-=heapq.heappop(values)

print(result)

보석을 모두 순회했다면 flag True로 만들어서 더이상 보석을 추가하지 않게 만들었다.

flag 사용말고도 wihle문이나 큐를 통해 원소를 제거하게 만들어도 괜찮을것같다