[Python] 백준 2258번: 정육점(시간복잡도 3등)

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

2258번: 정육점

import sys
input = sys.stdin.readline


def getMinCost(meats):
    # 무게에 대해서도 정렬해주는 것은, 같은 가격의 고기들을 살 때 고중량 고기를 먼저 사겠다는 것임
    meats.sort(reverse=True, key=lambda x: x[0])
    meats.sort(key=lambda x: x[1])

    weightCount = 0
    sameCostCount = 0
    costList = []

    for i in range(N):
        w, c = meats[i]

        weightCount += w
        # 1. 같은 가격인 고기들을 여러 개 살 경우
        if i >= 1 and c == meats[i-1][1]:
            sameCostCount += c
        # 2. 일반적인 경우, 이전 고기보다 현재 고기가 비쌀 경우
        else:
            sameCostCount = c

        if weightCount >= M:
            costList.append(sameCostCount)

            # 2의 경우인데 목표 중량을 달성했을 경우에는 더이상 반복문을 돌릴 필요가 없음
            if sameCostCount == c:
                break

    if costList:
        return min(costList)
    else:
        return -1


if(__name__ == "__main__"):
    # 입력
    N, M = map(int, input().split())

    meats = []
    for _ in range(N):
        meats.append(list(map(int, input().split())))

    # 처리
    minCost = getMinCost(meats)
    print(minCost)

문제를 처음 봤을 때, 매우 쉽게 풀 수 있을 거라는 직감이 들었으며 이게 실버 1이 맞나 싶었으나 그리 간단한 문제는 아니었다.

처음에는 반복문을 돌면서 현재까지의 무게를 누적합으로 더해가면서, M을 넘기는 순간 해당 고기의 가격을 출력해주면 된다고 생각했었다.

하지만, 이것은 '같은 가격의 고기'에 대한 처리를 해주지 않은 풀이이므로 오답이다. 가령, 아래와 같은 케이스에 대해서 처리가 되지 않는다는 것이다.

 

3 3000

1000 5

1000 5

1000 5

-> 15

 

3 3000

1000 1

1000 5

1000 5

-> 10

 

5 3500

500 1

1000 2

3000 2

2000 2

500 3

-> 3

 

5 5000

500 1

1000 2

3000 2

2000 2

500 3

-> 3(중요한 케이스이다. 여기서 3000, 2000 무게의 고기를 사서 4원이 나오면 안 된다.)

 

따라서, 고기에 대해 반복문을 돌 때, 현재 고기와 이전 고기가 같은 가격일 경우(#1)와 현재의 것이 더 비쌀 경우(#2)를 나누어 푼다.

위에 제시한 케이스에서 첫번째 케이스의 경우를 보자. 3000을 달성하기 위해 5원짜리 고기를 3번 구입한다. 이것을 위해 우리는 sameCostCount라는 변수를 활용한다. 같은 가격의 고기일 경우 sameCostCount를 현재 가격으로 누적합을 적용시키면 된다. 또한 #2의 경우에 sameCostCount를 현재 고기의 가격으로 초기화시켜준다. 이렇게 a번째 고기에서 초기화시켜주고 다음 a+1번째의 고기일 때, 해당 값을 이어받아서 여기에 c만 추가해주면 되기 때문이 이렇게 한 것이다.

이렇게 weightCount와 sameCostCount에 값을 처리해주었다. 다음은 누적된 무게가 M을 넘는지 확인하고, costList라는 곳에 sameCostCount를 추가해주면 된다. 여기서 무게를 넘기자마자 반복문을 끝내지 않는 이유는 위에서 제시한 마지막 케이스를 보면 설명된다. 따라서 최종 가격의 후보들을 costList에다 넣어주고 함수에 마지막 부분에서 최솟값을 출력해주면 된다.

그럼 마지막으로 남은 부분은 sameCostCount == c일 때 break를 해주는 것인데, 우선 해당 조건은, #2의 경우를 뜻한다. 왜냐하면 #2에서 sameCostCount = c로 삽입을 해주었기 때문이다. 그래서 결국에는 #2이면서 무게를 넘겼을 경우에는 더이상 연산을 하지 않겠다는 것이다. 이렇게 함으로써 시간에서의 이득을 취할 수 있는데, 이렇게 할 수 있는 것은,

1. 가격 같은 고기들 -> 비싼 고기

2. 비싼 고기 -> 가격 같은 고기들

3. 가격 같은 고기들이 없음

위의 두 경우에서 2번, 3번의 경우에는 무조건 1번이라도 무게가 충족되었으면 그것이 정답이기 때문이다. 애초에 1번의 경우 때문에 costList를 만든 것이다.