2258(정육점) - 해결

정육점

 

문제

은혜는 정육점에서 고기를 사려고 한다. 

보통 정육점에서는 자신이 원하는 양을 이야기하면 그 양만큼의 고기를 팔지만, 

은혜가 방문한 정육점에서는 세일 행사를 하고 있었기 때문에 N 덩어리의 고기를 이미 잘라놓고 판매하고 있었다.

 

각각의 덩어리들은 이미 정해져 있는 무게와 가격이 있는데, 어떤 덩어리를 샀을 때에는 

그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다(추가 비용의 지불 없이). 

또한 각각의 고기들은 부위가 다를 수 있기 때문에 비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다. 

은혜는 이러한 점을 고려하지 않고, 어느 부위든지 자신이 원하는 양만 구매하면 되는 것으로 가정한다. 

또한 만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다.

 

각 덩어리에 대한 정보가 주어졌을 때, 은혜가 원하는 양의 고기를 구매하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하시오.

 

입력

첫째 줄에 두 정수 N(1≤N≤100,000), M(1≤M≤2,147,483,647)이 주어진다. 

N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 

다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 음 아닌 두 정수가 주어진다. 

무게의 총 합과 가격의 총 합은 각각 2,147,483,647을 넘지 않는다.

 

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

---

여러가지 방법을 생각해보았다.

정렬을 통해 하는 방법 중 무게로 할 것인지, 가격으로 할 것인지 여러 생각을 해보았다.

가격을 내림차순으로하여 뒤에 합을 하던가, 무게를 오름차순 해서 더하면서 갈 것인가? 여러 방법을 생각해 보았을 때,

가격을 오름차순하고 무게를 내림차순하였다.

몇가지 문제들이 있었다.

1. 가격이 같은 경우/ 2. 무게가 같은 경우/ 3. 무게와 가격이 같은 경우

이와같은 세가지 경우가 문제였다. 그냥 세리게 하니깐 해당 부분들이 문제가 되었다.

같은 가격의 경우 가격을 추가해줘야했고 무게가 같은 경우에는 가격이 싼 것으로 정렬해서 해결 해보려고 하였다.

둘다 같은 경우에는 두 가지 경우를 합하여 해결해보고자 하였다.

#print(meats)
def sol():
    meatsum = 0
    pricesum = 0
    print(meats)
    for idx in range(1,len(meats)-1):

        #print("1",meatsum,pricesum)
        meatsum += meats[idx][0]
        #print("2",meatsum,pricesum)
        #print(meats[idx][0],meats[idx-1][0])
        if meats[idx][0] == meats[idx-1][0] or meats[idx][1] == meats[idx-1][1]:
            pricesum += meats[idx][1]
        else:
            pricesum = meats[idx][1]

        # if pricesum > meats[idx+1][1] and meats[idx+1][0] >= meatsum:
        #     meatsum = 0
        #     pricesum = 0
        #     continue
        # elif 

        print(meats[idx+1][1])
        if meatsum >= M:
            if pricesum > meats[idx+1][1] and meats[idx][1] != meats[idx-1][1] and meats[idx+1][1] :
                print("aa", meats[idx+1][1])
                pricesum = 0
                continue
            return pricesum

    return -1

이 경우 1,3을 통과하지 못하였다.

뒤에 더 비싼 걸 사면 되는데 그 전에 무게를 채워서 더 비싼 가격에 사버린다.

 

import sys

N, M = map(int,sys.stdin.readline().split())

meats = [tuple(map(int,sys.stdin.readline().split())) for _ in range(N)]

# 가격을 오름차순, 무게를 내림차순
meats.sort(key=lambda x: (x[1], -x[0]))
# 처음 원소를 생각해주기 위해
meats = [(0,0)] + meats
# 전의 값을 생각해주기 위해 DP처럼 해결

# 초기화
# 가격과 무게를 저장
dp=[]
for i in range(N+2):
    dp.append([0,0]) 

def sol():
    # 이거 보다 큰 값이 없기 때문
    minprice = 2147483647

    # 하지 못하는 경우를 파악하기 위해
    ck = True
    # 탐색
    for i in range(1,N+1):
        # 무게는 전의 것에 더하기
        dp[i][0] = dp[i-1][0] + meats[i][0]

        # 가격은 전보다 크다면 그대로 저장
        if meats[i][1] > meats[i-1][1]:
            dp[i][1] = meats[i][1]
        # 하지만 같다면 가격이 같기 때문에 더해준다.
        else:
            dp[i][1] = dp[i-1][1] + meats[i][1]
        
        # 무게가 원하는 무게보다 크다면 가격을 저장
        if dp[i][0] >= M:
            # 무게가 목표이상 올라가지 않으면 ck가 True
            ck = False
            # 해당 가격이 더 작다면 저장.
            if minprice >= dp[i][1]:
                minprice = dp[i][1]
    
    # -1 확인
    if ck:
        print(-1)
    else:
        print(minprice)

sol()

뭔가 그리디로 푼 느낌은 아닌 느낌?

브루트포스로 한거 같은데