-
1246. [Python]온라인 판매Python_알고리즘/Silver IV 2023. 4. 30. 23:17
1. 문제
https://www.acmicpc.net/problem/1246
1246번: 온라인 판매
첫째 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 입력된다. 둘째 줄부터 M+1번째 줄까지 i+1번째 줄에는 Pi(1 ≤ Pi ≤ 1,000,000)가 입력된다.
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 그리디 알고리즘
3. 파이썬 코드
N,M = map(int,input().split()) # 가격리스트를 생성 price_list = [] for _ in range(M): price_list.append(int(input())) # 가격리스트 오름차순 정렬 price_list.sort() # 각 가격대별 최대값 저장 answer = {} # M번만큼 반복하여 for i in range(M): # 0번 인덱스 부터시작해서 M 까지 반복하는데 계란의 갯수가 N개까지 밖에 없기 때문에 변수를 따로 구해준다. egg = M-i # 만약 달걀의 갯수가 N보다 큰경우 N 으로 바꿔준다. if egg > N: egg = N # 딕셔너리에 각 가격별 최대 값을 저장 answer[price_list[i]] = price_list[i]*egg # 최대 값을 변수로 저장 max_value = max(answer.values()) # value 값이 최대값인 경우 가격과 최대값 출력 for k,v in answer.items(): if v == max_value: print(k,v)
4. 문제를 풀고난 후 생각
- 가격별로 오름차순으로 정렬한 후 낮은 숫자부터 최대 몇명이 살 수 있는지와 최대 금액을 계산하는 것을 생각하고 구현했다.
- 처음 구현한 것은 N이라는 달걀 갯수를 고려하지 않고 코드를 작성하여 틀렸고, 이후 N이라는 달걀 갯수보다 살 수 있는 사람이 많아질 경우 (즉, N이 4 M이 5 일 경우 4명만 살 수 있는데 5명이 사고싶어하는 경우가 발생) 최대 N의 갯수로 변수를 재선언 해주는 방식으로 딕셔너리 형태로 값(Key), 최대금액(Value) 로 만들었다.
- 이후 딕셔너리에서 최대 값을 구한 다음 딕셔너리를 순회하며 value 값이 같은경우를 찾아서 Key, Value 를 출력했다.
5. 문제를 푸는데 도움이 되는 지식
- 그리디 알고리즘
- 딕셔너리
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
1487. [Python]물건 팔기 (0) 2023.05.04 1388. [Python]바닥 장식 (0) 2023.05.03 2003. [Python]수들의 합 2 (0) 2023.04.18 1639. [Python]행운의 티켓 (0) 2023.04.17 1337. [Python]올바른 배열 (0) 2023.04.13