[백준 2258] 정육점 (Python)

www.acmicpc.net/problem/2258

2258번: 정육점

 

문제풀이

N, M : 입력값

arr : (가격, 무게) 리스트

weight : 현재까지의 무게

same : 가격이 동일한 고기일 경우, 해당 가격만큼 결과에 더해주기 위한 변수

 

실버1 문제인데, 생각보다 많이 까다로운 그리디 알고리즘 문제였다. 처음에 우선순위 큐를 이용해 해결하려 하였는데, 계속 틀렸습니다를 받아서 결국 정답코드를 참고하였다.

생각보다 단순하게 생각하면 쉽게 해결할 수 있는 문제였다...

 

1. 고기 무게, 가격 입력 후 정렬하기

- (가격, 무게) 순으로 가격은 오름차순, 무게는 내림차순으로 정렬 => 앞에서부터 탐색하면서 가격은 적으면서 무게가 큰 고기를 선택하기 위함

 

2. 고기의 무게를 더해가면서 해당 고기가 이전에 탐색한 고기의 가격과의 일치 여부 확인하기 => 이 문제의 핵심 예외케이스

- 이전 고기의 가격과 일치할 경우 same 변수에 해당 값을 더하기

 

3. 현재까지 고기의 무게가 M 이상일 경우 결과값(ans) 갱신하기

- 현재까지 탐색한 고기 중 가격이 동일한 고기가 있을 경우 해당하는 값(same) 더하기

- 현재까지 고기의 무게가 M 이상이면서 최소의 가격으로 갱신

 

코드

import sys

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    arr = []

    for _ in range(N):
        a, b = map(int, sys.stdin.readline().split())
        arr.append((b, a))
    arr = sorted(arr, key=lambda x: (x[0], -x[1]))

    ans = sys.maxsize
    weight, same = 0, 0
    flag = False

    for i in range(N):
        weight += arr[i][1]
        if i >= 1 and arr[i][0] == arr[i - 1][0]:
            same += arr[i][0]
        else:
            same = 0
        if weight >= M:
            ans = min(ans, arr[i][0] + same)
            flag = True
    print(ans if flag else -1)

 

결과

 

위 풀이는 'hsdevelopment' 님의 Java 풀이를 참고한 코드입니다.

hsdevelopment.tistory.com/495

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!