백준 1049번 Python / Greedy

문제 링크

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

1049번: 기타줄

 

풀이

n,m = map(int, input().split())
prices = []
min_prices = []

for _ in range(m):
    prices += list(map(int, input().split()))

min_prices.append(min(prices[::2]))
min_prices.append(min(prices[1::2]))

if min_prices[0] > min_prices[1]*6:
    print(min_prices[1]*n)
else:
    print(min(min_prices[0]*(n//6)+min_prices[1]*(n%6),min_prices[0]*(n//6+1)))

우선 가장 적게 돈을 쓰는 것이 목표인 문제이기 때문에 6개짜리 패키지와 단일 품목들 중에서 가장 저렴한 가격만 각각 1개씩 골라서 min_prices 리스트에 넣었습니다.

 

이후에는 간단한 조건문을 통해서 답을 구할 수 있었습니다.

 

먼저, 단일 품목*6의 값(패키지 1개의 품목 수량)이 패키지 1개의 값보다 저렴하다면 구매하고자 하는 개수만큼 단일품목을 구매하면 됩니다. (단일 품목*6이 패키지보다 싸다면 패키지를 살 이유가 없다.)

 

위와 같은 예외 상황이 아니라면,

1. 패키지를 최대한 구매한 후(구매개수를 6으로 나눈 몫) 나머지를 단일 품목으로 구매하는 경우

2. 개수가 넘어가도 패키지로만 구매하는 경우(구매 개수를 6으로 나눈 몫 + 1)

1과 2의 상황의 가격을 비교해 더 작은 값을 출력해주면 됩니다.