[Python] 1049번 기타줄

✏️ 문제

 

문제 파악

min(6개입 가격)과 min(낱개 가격) 비교

• if min(6개입 가격) > min(낱개 가격) * 6 : 낱개로 전부 사는 게 이득
• if min(6개입 가격) < min(낱개 가격) * 6 : 6개 단위는 6개입으로 사는 게 이득
  • if min(6개입 가격) < min(낱개 가격) * 남은 개수(6개 이하) : 6개입을 하나 더 사는 게 이득
  • if min(6개입 가격) > min(낱개 가격) * 남은 개수(6개 이하) : 낱개로 사는 게 이득

 

알고리즘

• 그리디 알고리즘
• 수학

 

 

코드

n, m = map(int, input().split())
brand = []
money = 0

for i in range(m):
  brand.append(list(map(int, input().split())))
    
brand.sort()
min_value = min(min(subarray) for subarray in brand)

if n >= 6:
  if min_value * 6 < brand[0][0]: 
    money += min_value*n
  else:
    money += brand[0][0] * (n // 6)
    n %= 6    
    if brand[0][0] < min_value * n:
      money += brand[0][0]
    else:
      money += min_value * n
else:
  money += min_value * n

print(money)