[Python] BOJ/백준 1049번 기타줄

[문제]

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

1049번: 기타줄

 

[풀이]

첫 번째로 놓칠 수 있는 점은 기타 줄을 한 브랜드만 이용하지 않아도 된다는 것이다.

 

우선 가장 싼 패키지 가격과 낱개 가격을 package_price와 breakup_price 변수에 넣는다.

 

나올 수 있는 경우는 세가지 이다.

첫 번째) 패키지만 사용한 경우

두 번째) 섞어서 사용한 경우

세 번째) 낱개만 사용한 경우

 

끊어진 줄을 6으로 나눈 몫이 패키지로 구매 가능한 수량이다. 이를 package_cnt 변수에 담는다.

 

만약 7줄이 끊어졌을 경우

min(1개의 패키지로 구매했을 때, 6줄을 낱개로 구매했을 때)

+ min(1개의 패키지로 구매했을 때, 줄 1개를 낱개 구매했을 때)

로 전체 금액의 최솟값을 구할 수 있다.

 

[코드]

if __name__ == '__main__':
    n, m = map(int, input().split())
    brand = []
    for _ in range(m):
        package, breakup = map(int, input().split())
        brand.append([package, breakup])
    
    package_cnt = n // 6
    package_price, breakup_price = 1001, 1001
    for i in range(m):
        package_price = min(package_price, brand[i][0])
        breakup_price = min(breakup_price, brand[i][1])

    result = min(package_price * package_cnt, breakup_price * (6 * package_cnt))\
             + min(package_price, breakup_price * (n - package_cnt * 6))
    print(result)