그리디 알고리즘 한층 더 깊게 생각하는법 배우기 -선물할인-

1. 문제

 

25947번: 선물할인 (acmicpc.net)

25947번: 선물할인

 

n개의 선물 가격이 있고, 예산이 b원일때, 반값 할인을 a번 받을 수 있다면, 최대로 살 수 있는 선물의 개수는..?

 

2. 풀이

 

가장 먼저 생각한건... 가격표를 정렬하고 

 

큰 가격부터 a개는 반값으로 할인시킨다음에, 다시 정렬하고 b원만큼 사는 것

 

from sys import stdin

n,b,a = map(int,stdin.readline().split())

price = list(map(int,stdin.readline().split()))

price.sort()

answer = 0

for p in range(n-1,n-1-a,-1):
    
    price[p] = price[p]//2

price.sort()
    
for p in price:
    
    b -= p

    if b >= 0:
        
        answer += 1
    
    else:
        
        break

print(answer)

 

 

근데 이렇게 하면 당연히 틀린게, 큰 가격을 할인하는게 무조건 이득이냐를 생각해봐야겠다

 

극단적으로 보유 예산 b=1이고

 

선물 가격이 2 10 10 10 10 10이라고 해보면...

 

3번 할인 가능하다면.. 내 알고리즘대로는 2 10 10 5 5 5가 되어서... 정렬하면 2 5 5 5 10 10이고..

 

이러면 아무것도 못산다

 

하지만 실제로는 2원짜리를 1번 할인 받아서 1원으로 만들면 얘는 살수가 있다

 

그래서 다음으로...

 

일단 가격이 싼 것부터 사본다

 

예산이 음수가 된다면, 그동안 산 가격에서 비싼것부터 할인을 시도하고,

 

예산이 양수가 된다면 종료하고 다시 선물을 사들인다

 

할인할 수 있는 기회가 없다면, 더 이상 살수가 없다는 뜻이다.

 

from sys import stdin

n,b,a = map(int,stdin.readline().split())

price = list(map(int,stdin.readline().split()))

#할인을 한 물건인가 아닌가
visited = [0]*n

#가격 정렬
price.sort()

answer = 0

for i in range(n):
    
    #일단 가격이 싼 것부터 무조건 사들인다
    b -= price[i]
    
    #사고나서, 예산이 남아있다면 살수있다는 뜻
    if b >= 0:
        
        answer += 1
    
    #샀는데 예산이 음수가 된다면, 
    else:
        
        answer += 1
        
        #지금까지 산 물건중에서 반값 할인을 시도함
        find = False
        
        for j in range(i,-1,-1):
            
            #할인할 기회가 남아있고,
            if a > 0:
                
                #할인하지 않은 물건이어야함
                if visited[j] == 0:
                    
                    #물건을 샀을때, b - price[j]를 했으므로,
                    #j번째 물건을 할인해서 산것은, b + price[j]//2를 하면 된다
                    b += price[j]//2
                    visited[j] = 1

                    a -= 1
            
            else:
                
                break
            
            #예산이 양수가 된다면, 할인 종료하고 다시 물건을 사 들인다
            if b >= 0:
                
                find = True
                break
        
        #할인을 계속했는데도 예산이 양수가 안된다면
        #더 이상 살수가 없다
        if find == False:
            
            answer -= 1
            break
    
print(answer)

 

통과하긴 했는데... 시간이 너무 오래걸린다

 

 

3. 최적화된 풀이

 

최적화된 풀이중에서 이해하기 쉬운 풀이를 보면서 배워보자고

 

가격을 정렬하고, 가격 리스트의 개수 n만큼 for문으로 인덱스 순회

 

모든 물건을 절반가격만 주고 사기 시작한다.

 

인덱스가 할인 횟수 a이상이 된다면..

 

사들인 물건중에 가장 싼 물건 i-a부터 절반 가격을 더 줘서, 정상 가격으로 사들이기 시작한다.

 

그러다가 예산이 음수가 된다면.. 현재 물건은 살 수 없다는 뜻이므로..

 

인덱스는 0부터 시작하므로, 총 i개의 물건만 살 수 있다는 뜻이 된다.

 

n,b,a = map(int,input().split())

price = list(map(int,input().split()))

#가격 오름차순 정렬
price.sort()

#모든 물건을 다 살 수 있을때..
answer = n

#물건 사기 시도
for i in range(n):
    
    #모든 물건을 무조건 절반가격에 사들인다
    b -= price[i]//2
    
    #물건 할인 횟수 a 이상이 된다면,
    if i >= a:
        
        #가장 싼 물건부터 절반가격을 더 줘서, 정상가격으로 사들인다
        b -= price[i-a]//2
    
    #예산이 음수가 된다면..
    #현재 i+1개의 물건은 살 수 없다는 뜻이므로..(인덱스는 0부터 시작)
    #전체 i개의 물건을 살 수 있다는 뜻이다
    if b < 0:
        
        answer = i
        
        break

print(answer)

 

상당히 어렵네... 그리디 연습 많이해야겠는데