[백준][Python] 1049 기타줄

그리디 / 실버 4

🎸

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

1049번: 기타줄

 

내 풀이

N, M = map(int, input().split())

packages = []
pieces = []
ans = float('inf')

for _ in range(M):
    price1, price2 = map(int, input().split())
    packages.append(price1)
    pieces.append(price2)

# 패키지와 낱개의 최소 가격 추출 (다른 값은 필요 X)
min_package = min(packages)
min_piece = min(pieces)

# 될 수 있는 케이스 3개 (패키지로만, 패키지 + 낱개, 낱개로만)
ans = min(ans, min_package * (N // 6 + 1)) # 패키지로만 구입
for i in range(1, (N // 6 + 1)): # 패키지 + 낱개 구입
    ans = min(ans, min_package * i + min_piece * (N - (6 * i)))
ans = min(ans, N * min_piece) # 낱개로만 구입

print(ans)

 

처음에는 무조건 같은 브랜드로 조합해야 하는 줄 알았는데, 놉. 교차 구매가 가능하다!

즉, 패키지와 낱개를 혼합해서 구입하는 경우, 서로 다른 브랜드의 것을 선택할 수 있다.

↪ 전체 패키지의 가격 중 최솟값과 전체 낱개의 가격 중 최솟값만 도출해서 조합해 보면 된다. 다른 값들은 필요 없다.

 

조합할 수 있는 케이스는 3가지다.

 

1. 패키지로만 구입하는 경우

ans = min(ans, min_package * (N // 6 + 1))

 

2. 패키지 + 낱개 혼합 구입하는 경우

for i in range(1, (N // 6 + 1)):
    ans = min(ans, min_package * i + min_piece * (N - (6 * i)))

 

3. 낱개로만 구입하는 경우

ans = min(ans, N * min_piece)

 

가능한 모든 케이스를 검사한 후, 가장 작은 값이 정답이다.