[코딩테스트] 백준 1049번: 기타줄

-문제: https://www.acmicpc.net/problem/1049

 

총 구매 가격이 최소가 되는 것이 목표이므로 굳기 같은 브랜드별로 구매하지 않아도 된다.

6개 패키지 값이 제일 싼 브랜드와 낱개 값이 가장 싼 브랜드만 생각하면 된다

그래서 주어진 행렬에서 0열과 1열 0행에 가장 작은 값만 오면 된다(sort 두번 하면 됨)

그리고 모든 경우 다 계산해서 리스트에 넣고 가장 작은 값을 구하면 되는 줄 알았는데 그게 아니라 

경우에 따라서 나오는 최솟값이 다르므로 경우 설정을 해야 정답을 구할 수 있다는 것을 알았다. 

 

 

-정답풀이 1: 

n,k=map(int,input().split())
s=[]
for _ in range(k):
    s.append(list(map(int,input().split())))
six_list=sorted(s,key=lambda a: a[0])
one_list=sorted(s,key=lambda a: a[1])
a=n//6
b=n%6
ans=0
if six_list[0][0] <= one_list[0][1]*6:
    ans=(a)*six_list[0][0]+b*one_list[0][1]
    if six_list[0][0] < one_list[0][1]*(b):
        ans= (a+1)*six_list[0][0]
else:
    ans=n*(one_list[0][1])
print(ans)

1패키지의 값이 낱개 6개의 값보다 같거나 작은경우에는 주어진 갯수에 맞게 구매하는 것이 최소이고

1패키지의 값이 낱개 6개의 값보다 작은 경우에는 원래 개수를 초과하게 패키지를 구매하면 된다.

패키지의 가격이 6개의 값보다 큰 경우에는 모두 낱개로 구매한다 .

 

-정답풀이 2: 

내가 푼 풀이

0열 기준으로 정렬한 리스트와 1열 기준으로 정렬하는 리스트 각각 다른 리스트에 저장한다 

n,k=map(int,input().split())
s=[]
ans=[]
for _ in range(k):
    s.append(list(map(int,input().split())))
six_list=sorted(s,key=lambda a: a[0])
one_list=sorted(s,key=lambda a: a[1])
a=n//6
b=n%6
for i in range(k):
    ans.append((a+1)*six_list[i][0])
    ans.append((a*six_list[i][0]+b*one_list[i][1]))
    ans.append(n*one_list[i][1])
print(min(ans))

-틀린풀이:

60%까지 진행되다가 틀렸다

경우를 나누지 않아서 틀린 줄 알았는데, 알고보니 0열 기준으로 정렬하는 거랑 1열 기준으로 정렬하는 거 모두 다른 행렬로 만들어야했다. 

정답풀이 2를 참고하면 된다