백준 그리디 문제풀이 입니다.
문제
https://www.acmicpc.net/problem/1049
[나의 풀이]
N, M = map(int,input().split(' '))
pack = []
piece = []
cases = []
for i in range(M):
tmp = list(map(int,input().split(' ')))
# print(tmp)
pack.append(tmp[0])
piece.append(tmp[1])
if N%6 == 0:
cases.append(min(pack)*(N//6))
cases.append(min(piece)*N)
else:
cases.append(min(pack)*(N//6)+min(piece)*(N%6))
cases.append(min(pack)*(N//6+1))
cases.append(min(piece)*N)
# print(cases)
print(min(cases))
N개의 줄이 끊어진 상황에서 M개의 브랜드별 줄 패키지(6개) 가격, 낱개 줄 가격을 조합하여 최소값을 갖는 비용을 도출하는 문제입니다. 크게 두가지 경우의 수로 나누어 N%6 == 0일 때, 가장 저렴한 패키지로만 구매하거나 낱개로만 구매하는 경우와 N%6 != 0일 때, 패키지와 낱개를 조합하거나 패키지로만 N//6+1개 이상의 갯수를 구매하거나 낱개로만 N개 갯수를 구하는 경우의 수를 생각하여 최솟값을 도출하였습니다.🐨🐨🐨
[다른 사람의 풀이]
# n 끊어진 줄 개수
# m 기타줄 브랜드 수
# 1 패키지는 6줄
# 남은 줄의 갯수가 6보다 크다면 낱개가격*6 중 가장작은것과 패키지가격중 가장작은 것을 비교해 더 작은것을 리턴하고 남은줄-6
# 남은 줄의 갯수가 6보다 작다면 낱개가격*남은줄개수 중 가장작은것과 패키지가격을 비교해서 더 작은것을 리턴
n, m = map(int, input().split())
package = []
single = []
for _ in range(m):
a, b = map(int, input().split())
package.append(a)
single.append(b)
min_package = min(package)
ans = 0
while n > 0:
if n >= 6:
min_single = min(single)*6
n -= 6
else:
min_single = min(single)*n
n -= n
if min_single < min_package:
ans += min_single
else:
ans += min_package
print(ans)
다른 사람의 풀이로는 위와 같이 N이 6이상일 때 먼저 (6* 가장 저렴한 낱개)의 가격을 구하고 이를 가장 저렴한 패키지 가격과 비교하여 더 작은 비용을 더하는 방식이었습니다🐢🐢🐢
감사합니다.