[알고리즘/그리디] 1758번 : 알바생 강호 - python

링크 : https://www.acmicpc.net/problem/1758

1758번: 알바생 강호

 

---

• 문제
• 소요시간: 17분 19초

---

• 설계하기(접근방법) 

1. 입력받기

더 이상 입력이 없을 때까지 입력받는다

2. 해석

이 문제의 핵심은 작은 수를 후순위에 두는 것이다.

어차피 받지 못하는 팁이라면

ex)7번째 순서라고 했을 때

1 - 6 = -5

6 - 6 = 0 

1원과 6원은 같은 취급을 받는다.

즉 음수는 가능한한 작게 해도 0으로 취급받기 때문에 작은 수들을 뒤에 몰아넣어야 한다. = 내림차순 정렬

최대한 6원을 앞에 배치하여 양수를 많이 가져가는 것이 이득이다

따라서 큰 순서대로 정렬하여 순서대로 가져가면 된다.

 

반복문을 통해 하나씩 더해 나가며, 음수가 나온다면 break를 통해 반복문을 빠져나온다

 

3. 출력

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

n = int(input())

money = []
result = 0

for i in range(n):
    money.append(int(input()))

money.sort(reverse=True)

for i in range(len(money)):
    if money[i] - i < 0:
        break
    result += money[i] - i

print(result)

 

---

• 얻어갈 부분

1. 문제를 잘못 읽어 더 이상 입력이 없을 때까지 입력을 받는줄 알고 try except문을 쓰다가 한 번 틀렸다. 조심하자