[백준 python] 1049번 기타줄 - 그리디

[백준 python] 1049번 기타줄 - 그리디

레벨: 실버 4

언어: 파이썬

---

문제풀러가기

📑풀이 과정

이 문제는 몇 가지의 경우를 찾아서 계산해주면된다.
input을 받으며 가장 싼 패키지와 가장 싼 낱개 가격을 찾아주고 나머지 값은 저장할 필요가 없다.

아래 경우에서 적은 패키지와 낱개는 모두 가장 값이 싼 것을 기준으로 설명한다.

1. 패키지의 가격이 낱개 X 6 보다 비싼 경우
   -> 이런 경우는 모든 N을 낱개 가격으로 구매하면 된다.(N * 낱개)
2. 1번이 아닌 경우라면
   -> 최대한 만은 패키지를 구매한다. (N // 6 * 패키지 만큼)
3. 그 후 남은 기타줄의 수가 패키지로 구매하는게 저렴한지 낱개로 사는게 저렴한지 비교해서 저렴한 것으로 구매하면된다.

코드는 주석으로도 충분히 설명이 될거 같아 따로 적지 않겠다.

📋풀이 코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split(' '))

minPack = 1001 # 주어지는 입력보다 더 큰 값으로 초기화
minSingle = 1001
for i in range(M):
  p, s = map(int, input().split(' '))
  minPack = min(minPack, p)
  minSingle = min(minSingle, s)

result = 0

# 패키지가 낱개 X 6 보다 가격이 크면 낱개로 모두가 구매한다.
if minPack > minSingle*6:
  result += N * minSingle
else:
  # 패키지가 더 저렴할 때
  # N을 6으로 나눈 몫 만큼 패키지로 구매 한다
  result += (N//6) * minPack

  # 남은 낱개의 가격이 패키지 보다 크면 패키지를 구매하고 아니면
  # 낱개로 구매한다.
  if (N%6)*minSingle > minPack:
    result += minPack
  else:
    result+= (N%6)*minSingle

print(result)

---