[BOJ - 그리디] 1049번 : 기타줄 ( python )

백준알고리즘 1049번 기타줄 그리디(greedy) 실버 4 파이썬

 

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

1049번: 기타줄

 

 

문제

Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

 

---

 

그리디 안푼지 오래돼서 실버 4부터 풀어봤다. 

 

 

1. 이 문제를 공유한 이유 : 조건/ 주석/ 가독성의 중요성

 

알고리즘 문제를 풀면서 가장 중요한것은 역시 생각을 먼저하고 조건을 완벽하게 생각하는 것 아닐까 하는 생각이 드는 요즘이다.  항상 안풀리는 문제는 조건이 완벽하지 않았기 떄문이라는 걸 다시 느끼게 해준 문제라서 이 문제를 공유했다. 

 

또 최근에 알고리즘 문제풀때 내가 이렇게 왜 풀었는지 모르는 사람들이 많다는 영상을 봤다. 

입출력에만 의존해 문제를 풀다보니 결과적으로 가독성과 코드 효율이 떨어지고, 자신도 왜 이렇게 썼는지 모르는 사람들을 이야기 하는데 솔직히 찔렸다. 

 

조건을 생각하고 주석처리를 해놓은담에 그 위치에 코드를 작성하면 중간에 내가 갑자기 머리가 멍해지더라도 어디까지 했는지 명확하게 알수 있다고 해서 나도 오늘부터는 이렇게 해야지 하면서 문제를 풀어봤다. 

 

또 알고리즘 문제 풀떄 당연히 변수명을 쉽게 li, cnt, a, b 이런식으로 해도 되지만, 가독성을 높이기 위하여 변수명을 좀 제대로 작성해봐야지 하면서 변수명을 가독성있게 바꿔보았다. 

 

 

나중에 실전 코딩테스트에서도 가독성 있는 코드를 만들기 위해 이제부턴 변수명에 꼭 신경을 써야겠다. 

 

2. 사고하기

끊어진 기타줄 N개를 살건데

브랜드는 M개 있고 브랜드마다 6개를 한패키지로 판매한다. 

가장 최소가격으로 N개를 산다고 할떄 가격을 구하시오

 

이 문제를 보자마자 조건을 어떻게 생각했냐면,,

 

1) 여러 브랜드에서 낱개판매가 중 가장 싼 가격을 * 6 했을 때 

가장 싼 패키지가보다 작으면 >> 낱개로만 구매하면 된다.

 

2) 낱개판매가 중 가장 싼 가격을 * 6 했을 때

가장 싼 패키지가보다 크면 >> 패키지 최소가로 최대한 구매할 수 있을 때까지 구매하고 나머지는 낱개최소가로 산다.

 

3) 만약 나머지개수 * 낱개 최소가가 패키지로 사는가격보다 크면 패키지 한개를 더 추가해 패키지로만 구매하면 된다. 

 

 

 

생각 먼저하고 주석으로 적어놓은 다음에 코드를 적으니까 한방에 맞을 수 있었다. 

 

정답 코드

#1049_기타줄_greedy_silver4

import sys
input = sys.stdin.readline

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

pricePackage =[[0] for _ in range(m)]
priceOne = [[0] for _ in range(m)]

for i in range(m):
    package, one = map(int,input().split())
    pricePackage[i] = package
    priceOne[i] = one

minOne = min(priceOne)
minPackage = min(pricePackage)

NumOfPackage, NumOfOne = 0,0
if minOne * 6 >= minPackage: #패키지 가격이 제일 쌀떄
    NumOfPackage = n // 6
    NumOfOne = n % 6
    
    if minPackage <= (NumOfOne * minOne): #나머지 개수를 개당 가격으로 곱했는데 패키지 가격보다 비싸면 그냥 패키지 한개 사주고 개당은 안삼
        NumOfPackage +=1
        NumOfOne = 0
else:
    NumOfOne = n

print(NumOfPackage * minPackage + NumOfOne * minOne)