[Baekjoon] 백준 알고리즘: 1049 - 기타줄

문제

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

1049번: 기타줄

내가 생각했던 풀이과정

 

1. 예제 출력 2로 확인한 결과 꼭 같은 브랜드의 6개묶음과 낱개묶음을 사야하는 것이 아닌 브랜드를 섞어서 구매해도 된다는 것을 알아서, 

2. 각 브랜드별로 6개 묶음의 가격과 낱개 가격을 입력받을 때 앞의 입력에는 6개 묶음 배열에, 뒤의 입력에는 낱개 묶음 배열에 추가해준다

3. 필요한 돈의 수를 최소로 하기 때문에 그리디를 생각해서, 6개 묶음 배열에서 가장 최소값과 낱개 묶음 배열에서 가장 최소값을 찾는다

4. 

가격을 3가지를 비교해야한다

1) 갯수를 맞춰서 사지만 6개 묶음과 낱개를 섞어서 사는 방식

A = 6개 묶음의 최소값 * N을 6으로 나눈 몫 + 낱개 묶음의 최소값 * N을 6으로 나눈 나머지

2) 갯수를 맞춰서 사지만, 낱개를 N개 사는 방식

B = 낱개 묶음의 최소값 * N

3) 갯수는 넘치지만, 6개 묶음으로 샀을 때 1), 2) 보다 싼 방식

C = (N을 6으로 나눈 몫 + 1) * 6개 묶음의 최소 값

 

A, B, C에서 최소 값을 출력한다

나의 풀이

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

blist = []
plist = []
for i in range(M):
    bundle, piece = map(int, input().split())
    blist.append(bundle)
    plist.append(piece)

min_blist = min(blist) # 6개 묶음에서 최소값 찾기
min_plist = min(plist) # 낱개 묶음에서 최소값 찾기

share = N // 6 # 몫
remain = N % 6 # 나머지

A = share * min_blist + remain * min_plist
B = min_plist * N
C = (share + 1) * min_blist

print(min(A, B, C))

다른 사람의 풀이

# 1049번

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

answer = 0
price_list = []

for _ in range(m):
    price = tuple(map(int, input().split()))
    price_list.append(price)

six_list = sorted(price_list, key=lambda x : x[0])
one_list = sorted(price_list, key=lambda x : x[1])

if six_list[0][0] <= one_list[0][1] * 6:
    answer = six_list[0][0] * (n // 6) + one_list[0][1] * (n % 6)
    if six_list[0][0] < one_list[0][1] * (n % 6):
        answer = six_list[0][0] * (n//6 + 1)
else:
    answer = one_list[0][1] * n

print(answer)

튜플을 저장하면서 각각의 가격을 저장한다.

sorted( )함수인 lambda를 이용하여 key를 x[0]으로 저장한 점과, key를 x[1]로 저장을 하셨다.

그 후 로직은 나랑 비슷하지만 나와 같다.

새로 알게된 점, 확인해야할 점