백준/그리디

[백준] 1758번, 알바생 강호 - Python

CoGam 2024. 2. 6. 00:24
728x90

 

거스름돈 문제와 앞선 ATM문제를 풀다보니 이 문제를 읽었을 때는 그리디 문제라는 것이 눈에 보였다.

 

 

문제 이해

강호가 손님을 입장시킬 때 팁을 받는다.

 

손님들이 생각하고 있는 팁의 금액이 주어진다.

 

하지만 이 팁을 다 받을 수 있는 것이 아니다.

 

최종적으로 받는 팁 = 원래 생각하던 팁 - (손님의 입장 등수 - 1)

 

즉 원래 생각하던 팁은 주어져 있기 때문에 우리가 바꿀 수 있는 것은 "손님의 등수" 라는 것을 쉽게 알 수 있다.

 

문제의 출력으로 원하는 것은 강호가 받을 수 있는 팁의 최댓값이다.

 

손님의 등수를 기준으로 매 순간 최선의 선택을 해야한다는 것을 알 수 있다.

 

 

해설

내가 가장 먼저 떠올렸던 방법은 ATM에서 이용했던 방법이다.

 

처음부터 공식이 정해져있기 때문에 세로로(?) 누적해서 더한다는 생각을 하였다.

 

예를 들어,

N = 3이고

생각하는 팁이 3, 3, 2 이라고 가정하자.

팁의 관점에서 [3,2,3]으로 손님들의 순서가 정해진다고 했을 때 공식에 적용하면

 

최종 팁 = {3 - (1 - 1)} + {2 - (2 - 1)} + {3 - (3 - 1)} = 5 가 된다.

 

이 식을 세로(?) 관점에서 다시 써보면

 

최종 팁 = (3+2+3) - {(1+2+3) - 3} = 5 로 쓸 수 있다.

 

붉은색: 생각하는 팁의 총합

파란색: 1등부터 N등까지 있으므로, 1부터 N까지의 합

노란색:  (-1) * N

 

한번쯤 생각해볼만 한 것 같다.

 

하지만 당연하게도 커다란 허점이 존재한다.

 

바로 공식을 썼을 때 누군가에게 음수의 팁을 받을 수 있다는 점이다. 처음 생각대로 풀려면 각 사람마다 최종적으로 주는 팁이 양수로 보장되어야한다. 물론 이 경우에는 최댓값이라는게 존재하지 않을 것이다 (처음부터 틀린 관점인 것이다).

 

따라서 누적(총합)으로 보는 것이 아니라 각각 사람들의 최종 팁을 계산해서 합치는 방식을 택해야 하고 그때마다 최선의 선택을 해야하는 것이다.

 

그렇다면 당연하게도 가장 큰 팁을 생각하는 사람을 가장 앞 등수로 입장시켜야한다. 이것이 최종적으로 강호의 팁을 최대로 만들어주는 이유는, 음수의 팁을 생각해보면 된다. 

 

문제에서는 팁이 음수이면 0원으로 계산하라고 하였다. 

 

여러 명이 있다고 가정하자.

  • 5원을 생각하는 사람이 1등으로 들어오면, 강호에게 5원을 줄 것이다.
  • 5원을 생각하는 사람이 2등으로 들어오면, 강호에게 4원을 줄 것이다.
  • 5원을 생각하는 사람이 5등으로 들어오면, 강호에게 1원을 줄 것이다.
  • 5원을 생각하는 사람이 7등으로 들어오면, 강호에게 0원을 줄 것이다.

 

  • 1원을 생각하는 사람이 1등으로 들어오면, 강호에게 1원을 줄 것이다.
  • 1원을 생각하는 사람이 5등으로 들어오면, 강호에게 0원을 줄 것이다.

우리는 강호에게 최대의 이득을 주기 위해서 손실을 최소로 하여야한다. 

 

돈을 처음부터 많이 주려던 사람은 등수가 밀릴수록 우리가 받을 수 있는 금액이 조금씩 줄어드는 결과를 낸다. 우리의 손해가 오래 지속된다는 의미이다.

 

돈을 처음부터 적게 주려던 사람은, 등수가 밀린다면 어느정도 손실이 있지만 금새 0원으로 바뀐다. 즉 어차피 손해를 입어야한다면, 그리고 어떤 손님에게는 팁을 받지 못해야한다면 돈을 많이 주려던 사람보다는 적게 주려던 사람이 더 가성비가 좋다는 이야기이다. 어느 순간부터는 우리의 손해가 아니라 그저 0으로 치환되기 때문이다.

 

 

실제 코드

N = int(input())

think = sorted([int(input()) for _ in range(N)], reverse=True)

total_tip = 0
for idx, tip in enumerate(think):
    if tip - idx <= 0:
        break

    total_tip += tip - idx

print(total_tip)

 

요즘 시간을 조금 단축시키려고 리스트 컴프리헨션을 쓰다보니 가독성이 조금은 떨어질 수 있을 것 같다.

 

그래도 간단한 코드라 따로 풀어서 쓰지는 않았다.

 

우리가 우선적으로 처리 할 사람은 돈을 많이 줄 사람들이기 때문에 입력받은 팁을 내림차순으로 정렬하였다.

 

ATM에서도 마찬가지였지만, 시간을 더 줄이려면 reverse를 따로 쓰지 않는 코드도 고려해볼 만 할 것이다.

 

이후 문제에서 살펴본 최종 팁 공식에 순서가 들어가기 때문에 enumerate()를 이용하여 index와 tip을 큰 순서대로 가져와서 total_tip 변수에 공식대로 더해주었다.

 

오름차순으로 정렬되어 있기 때문에 누군가의 팁이 0 이하로 내려간다면, 그 이후의 값은 모두 0 이하가 될 것이기에 바로 for문을 빠져나오도록 처리했다.

 

 

시간 복잡도

총 주어진 시간이 2초이고 N의 범위는 1 <= N <= 100,000 이다.

 

NlogN 안에 문제를 해결해야함을 알 수 있다.

 

sorted() 함수는 O(NlogN),

for문은 O(N) 이내로 고려할 수 있다.

 

따라서 총 시간 복잡도는 O(NlogN)이 된다.

반응형