[알고리즘/그리디] 1049번 : 기타줄 - python

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

1049번: 기타줄

 

---

• 문제
• 소요시간: 25분 실패

---

• 설계하기(접근방법) 

1. 입력받기

 

2. 구현하기

 

1. 세트 1개가 낱개 1개보다 싼 경우 or 일정 범위부터 나머지 낱개 대신 세트로 사는게 저렴한 경우

 -> 모두 세트로 구하기

 

2. 세트 1개가 낱개 6개보다 비싼 경우 -> 세트를 사지 않는다

-> 모두 낱개로 구하기

 

3.세트 랑 낱개를 섞어서 사는 경우

-> 섞어서 구한다

 

3. 출력하기

3 가지 중에 min값을 출력한다

 

---

• 코드(출력)

n, m = map(int, input().split())
set_6 = []
ind = []

for _ in range(m):
    a, b = map(int, input().split())
    set_6.append(a)
    ind.append(b)

# 가장 저렴한 세트와 낱개 가격을 찾습니다.
set_6.sort()
ind.sort()

# 세트로만 구매하는 경우와 남은 개수를 낱개로 구매하는 경우의 비용
cost_with_set = set_6[0] * (n // 6) + ind[0] * (n % 6)
# 모두 세트로 구매하는 경우 (남은 개수가 있더라도 추가 세트 구매가 더 저렴할 수 있음)
cost_all_set = set_6[0] * ((n + 5) // 6)
# 모두 낱개로 구매하는 경우
cost_all_individual = ind[0] * n

# 최소 비용 계산
answer = min(cost_with_set, cost_all_set, cost_all_individual)

print(answer)

---

• 얻어갈 부분

1. 꼭 케이스를 내가 나누지 않고 min처리해도 쉽게 구할 수 있다