-
1758. [Python]알바생 강호Python_알고리즘/Silver IV 2023. 5. 11. 23:16
1. 문제
https://www.acmicpc.net/problem/1758
1758번: 알바생 강호
첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 256MB
- 정렬
- 그리디 알고리즘
3. 파이썬 코드
import sys input = sys.stdin.readline # 들어오는 input의 갯수 N = int(input()) # 가격 리스트 생성 pay_list = [] # N만큼 리스트 반복 for _ in range(N): pay_list.append(int(input())) # 리스트 역순 정렬 pay_list.sort(reverse=True) # 총가격 변수 total_pay = 0 # 인덱스와 값을 순회하며 값을 더해나감 음수일 경우 이후로도 음수이기 때문에 break for i,v in enumerate(pay_list): pay = v - i if pay >= 0: total_pay += pay else: break print(total_pay)
4. 문제를 풀고난 후 생각
- 최대의 이득을 내기 위해서는 큰 값과 작은 등수를 빼줘야 한다는 생각을 했다.
- 들어온 값들의 리스트를 내림차순으로 정렬한 후 enuermate 를 이용하여 리스트의 인덱스 번호와 값을 동시에 반환해주며 만약 음수가 나오기 시작했다면 이후 계속 음수이기 때문에 음수가 나오면 break를 걸어서 쓸데없는 반복문을 돌지 않게한다.
5. 문제를 푸는데 도움이 되는 지식
- 그리디 알고리즘
- 정렬
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
1544. [Python]사이클 단어 (0) 2023.05.15 2090. [Python]조화 평균 (0) 2023.05.14 1487. [Python]물건 팔기 (0) 2023.05.04 1388. [Python]바닥 장식 (0) 2023.05.03 1246. [Python]온라인 판매 (0) 2023.04.30