[Python] 백준 1049번 - 기타줄

1049번: 기타줄

 

문제

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

 

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의

가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

 

n, m = map(int, input().split())
cost = [1000, 1000]
for _ in range(m):
    p, e = map(int, input().split())
    if cost[0] > p:
        cost[0] = p
    if cost[1] > e:
        cost[1] = e

if n % 6 <= 0:
    cost[0] = cost[0] * (n // 6)
    cost[1] = cost[1] * n
else:
    cost.append(n * cost[1])
    cost[1] = cost[0] * (n // 6) + cost[1] * (n % 6)
    cost[0] = cost[0] * (n // 6 + 1)
    
    
print(min(cost))

이 문제는 조건을 잘 적용해주시면 풀 수 있는 문제입니다! 가장 중요한 것은 한 브랜드에서 6줄짜리 패키지와 낱개줄을 사용해야 하는것이 아닙니다. 6줄짜리 중에서 제일 싼 가격인 브랜드와 낱개줄에서 가장 싼 가격을 기준으로 정답을 구하는 것이기 때문입니다!

 

- 저는 cost라는 리스트 가격의 최댓값인 1000으로 초기화했습니다.

- m의 개수만큼 for문이 돌면서 cost에는 최소값을 넣는겁니다. 6줄짜리 패키지인 p와 낱개줄인 e를 따로 저장해줍니다.

- 그러면 cost에는 입력받은 브랜드의 6줄, 낱개줄 가격의 최솟값만 남게됩니다.

- 그 다음에는 경우를 나누어 생각해줬는데요.

• n, 즉 교체해야하는 기타줄이 6의 배수이거나 6 미만인 경우 → 6줄짜리에 n을 나눈 몫을 곱해주고 낱개줄에는 n을 바로 곱해주면 됩니다. 6의 배수라면 6줄짜리나 낱개가 남을 일이 없어 교차해서 사용할 필요가 없고, 6개 미만이라 할지라도 서로 교차해서 사용하는 경우가 없기 때문입니다.
• n이 6보다 크면서 배수가 아닌 경우 → 이 때는 고려해야할 요소가 3가지로 늘어납니다. 

1. 6줄짜리만 사용한 경우의 가격
2. 6줄짜리 n // 6개와 낱개줄 n % 6개를 교차해서 골랐을 경우의 가격
3. 낱개줄만 사용한 경우의 가격

- 위에 나열된 경우를 if문으로 나누어놓으면 cost에 저장된 값 중에서 최솟값이 정답이 됩니다.

 

피드백은 언제나 환영합니다.