1049

날짜 : 2022. 10. 19

사용 언어 : python

 

문제

 

 

코드

import sys

n, m = map(int, sys.stdin.readline().split()) # 끊어진 기타줄, 브랜드 개수
pack, ea = 1000, 1000 # 가격
cnt_p, cnt_e = 0, 0 # 세트와 낱개의 개수

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    pack = min(a, pack)
    ea = min(b, ea)

cnt_p = (n // 6)

if ea * 6 <= pack : # 세트가 낱개 * 6보다 비싼 경우
    print(n * ea) # 전부 낱개로 구매
else:
    if (n % 6) == 0:
        print(cnt_p * pack)
    else:
        cnt_p += 1
        cnt = 0
        for i in range(cnt_p, -1, -1):
            if i == cnt_p:
                price = cnt_p * pack
            else:
                cnt_e = (n % 6) + (cnt * 6)
                cnt += 1
            tmp = i * pack + cnt_e * ea
            if price > tmp:
                print(tmp)
                break
        else:
            print(price)

 

 

알게된 점

- 아침에 머리깨우는 용도로 풀기위해 선택했는데 의외로 많이 걸렸다.

- 단순 그리디 알고리즘이었지만 중간에 끊어진 기탓줄이 6의 배수인 테스트케이스를 가격 계산 과정에서 누락해서 꽤 시간이 걸렸다.

 

 

참고 사이트

-