💬 Comment
- 할 수 있는/ 선택할 수 있는 어떤 선택지들이 여러 개 있고 (Ex. 거스름돈이 여러 개 / 사거나 교체하거나 / 버튼이 여러 개.. )
- 그 중 어느 선택을 하느냐에 따라 ⇒ 값 ( 비용/갯수/횟수 ) 가 달라진다 , 각 값이 다르니까!
- 근데, 이 값 을 최소/최대로 하고 싶다 ⇒ 그리디를 고려해보기
🔑 Solution
돈을 최소로 쓸려면
- 6개팩을 선택하느냐 OR 낱개를 선택하느냐, 더 저렴한걸 선택하는게 목적
저렴하려면
- 일단 각 브랜드중에서 낱개가 젤 저렴한거 고르고, 팩이 젤 저렴한걸 골라볼 수 잇다
데이터 저장하는 DS
- 각 브랜드별 리스트가 아니라 → 팩에 대해 list 한개, 낱개에 대해 list를 한개
- 가장 저렴한걸 찾기 위해 정렬
팩에서 젤 저렴한값 ↔ 낱개에서 젤 저렴한 값 비교하기
- “6개” ← 숫자로 주는 거 “조건”으로 보자!
- 이때, 낱개로 6개하는게 더 저렴하면, 전부 낱개로 사면 해결
- 문제는 6개팩이 더 저렴할 때 ⇒ 그러면 최대한 팩으로 사고, 나머지를 낱개로 사면된다
팩으로 살 수 잇을 만큼 사고, 나머지에 대해 처리하기
- 근데 “적어도 N개”라고 했으니 더 사도 된다
- 팩으로 사는게 더 저렴한지, 낱개가 더 저렴한지 계산해보고 마지막 값을 구하면 된다
👉 문제 곳곳에 숫자와, “적어도”와 같은 표현 → 문제해결에 필요한 조건들이다.
# 2초 / 128MB
# 돈을 적게 쓰려고 함
# 6줄 패키지 OR 1개 또는 그 이상의 줄을 낱개로 살 수 있음
# 목적
# 적어도, N개를 사기 위해 필요한 "돈의 수"
import sys
input = sys.stdin.readline
# N : 끊어진 기타줄의 갯수 : 1이상, 100이하
# M : M개의 브랜드 : 1이상, 50이하
N, M = map(int, input().split())
pack_list = []
each_list = []
for m in range(M):
# DS : 패키지 따로, 낱개 배열 따로 저장
# 각 브랜드에서 파는 패키지가격 / 낱개 가격
pack, each = map(int, input().split())
pack_list.append(pack)
each_list.append(each)
# 각 배열 정렬 # 20, 40, 60 # 4, 7, 8
pack_list.sort()
each_list.sort()
# 6개 단위에 대해서 먼저 비교 # 20 vs 4 * 6 => 20
min_pack_val = 6006
ans_cost = 0
# 패키지가 더 저렴하면,
if pack_list[0] < each_list[0] * 6:
# N // 6 만큼 패키지로 지불
ans_cost += (N // 6)* pack_list[0]
# 남은 거에 대해서 재계산
ans_cost += min((N % 6) * each_list[0], pack_list[0])
# 낱개가 더 저렴하다면,
else:
# 모든 기타줄을 낱개로 지불
min_pack_val = each_list[0] * 6
ans_cost += N * each_list[0]
print(ans_cost)