코드

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

brand = []

# 6개 패키지 가격, 개당 가격
for _ in range(m):
    brand.append(list(map(int, input().split())))
    
def solution(brand):
    
    # 6개 패키지의 최솟값
    min_six = 1001
    
    # 패키지 구매와 개당을 6개 산 것 중 가장 싼 값을 저장
    for i in range(m):
        min_six = min(min_six, brand[i][0], brand[i][1] * 6)
        
    # 1개의 최솟값
    min_one = 1001
    
    # 개당 가격이 가장 싼 값을 저장
    for i in range(m):
        min_one = min(min_one, brand[i][1])
        
    # a : 패키지 구매 개수
    # b : 개당 구매 개수
    a = n // 6
    b = n % 6
    
    # 아래 조건식의 뜻
    # 개당 구매 개수의 총 가격이
    # 패키지로 사는 것보다 비싼 경우
    # 그냥 패키지를 하나 더 사고 만다
    if b * min_one > min_six:
        print((a+1) * min_six)

    # 그렇지 않다면
    # 패키지 개수만큼 사고, 개당 남은 개수를 구매
    else:
        print(a * min_six + b * min_one)
    
solution(brand)

문제 해설

그리디 알고리즘 문제.

함정이 문제에 존재하여 1차원 적이게 생각하면 오답이 높다. (내가 그랬음..ㅠㅠ)

위 문제에서 조심해야 할 함정은 아래와 같다.

  1. 무조건 패키지 가격이 개당 * 6의 가격보다 싼 것이 아니다.
  2. 패키지로 사고 남은 개수가 6개 미만인 경우, 남은 개수 * 개당 가격이 패키지 하나의 가격보다 비싼 경우가 존재한다.

2번 함정은 처음부터 간과하고 들어가서 오답을 3번이나 판정받았다ㅠㅠ…

위 두 부분만 조심한다면, 구현 자체에는 별다른 어려움이 없기 때문에 자세한 설명은 주석으로 대신하겠습니다!!

댓글남기기

참고