백준 1049번 기타줄

https://www.acmicpc.net/problem/1049

1049번: 기타줄

 

그리디 알고리즘을 이용하면 쉽게 풀 수 있는 문제이다.

단순히 기타줄 세트와 낱개의 가격에서 가장 저렴한 비용만을 이용하면 쉽게 해결이 되는 문제이다.

최소가격을 결정하는 케이스는 3개뿐이라 3개의 케이스를 모두 계산을 해서 다시 최소값을 구하면 되는 문제이다.

import sys
input = sys.stdin.readline

n, m = map(int,input().split())

set_list = []
each_list = []
for _ in range(m):

    a, b = map(int,input().split())
    set_list.append(a)
    each_list.append(b)

set_list.sort()
each_list.sort()

# 3가지 케이스가 존재함
# 그냥 낱개로 사기
# 그냥 세트로 다 사버리기
# 세트로 살수있는 만큼만 사고 나머지는 낱개로 사기

each_price = each_list[0]*n
number = n // 6
if n % 6:
    number += 1
set_price = set_list[0] * number
number = n // 6
set_with_each_price = set_list[0]*number + each_list[0]*(n%6)

print(min(each_price, set_price, set_with_each_price))