[ 코드업 ] Greedy

문제집 / 그리디

 

[ 2001 ] 최소 대금

※ 문제

파파 파스타 가게는 점심 추천 파스타와 생과일 쥬스 세트 메뉴가 인기가 좋다. 이 세트 메뉴를 주문하면 그 날의 3 종류의 파스타와 2 종류의 생과일 쥬스에서 하나씩 선택한다. 파스타와 생과일 쥬스의 가격 합계에서 10%를 더한 금액이 대금된다. 어느 날의 파스타와 생과일 쥬스의 가격이 주어 졌을 때, 그 날 세트 메뉴의 대금의 최소값을 구하는 프로그램을 작성하라.

 

※ 입력

입력은 5 행으로 이루어지며, 한 줄에 하나씩 양의 정수가 적혀있다.

1행의 정수는 첫 번째 파스타 가격이다.

2행의 정수는 두 번째 파스타 가격이다.

3행의 정수는 세 번째 파스타 가격이다.

4행의 정수는 첫 번째 생과일 쥬스 가격이다.

5행의 정수는 두 번째 생과일 쥬스의 가격이다.

(모든 파스타와 생과일 쥬스의 가격은 100 원이상 2000원 이하이다.)

 

※ 출력 

그날 세트 메뉴의 최소 대금을 소수 첫째자리까지 출력하시오.

# 최소대금
pasta = []
p = 3

juice = []
j = 2

for i in range(p):
    pasta.append(int(input()))
pasta_min = min(pasta)

for i in range(2):
    juice.append(int(input()))
juice_min = min(juice)

result = (pasta_min + juice_min) * 1.1
result_cal = round(result, 2)

print(result_cal)

입력 

800

700

900

198

330

 

출력 

987.8

 

[ 3120 ] 리모컨

※ 문제

컴퓨터실에서 수업 중인 정보 선생님은 냉난방기의 온도를 조절하려고 한다.

냉난방기가 멀리 있어서 리모컨으로 조작하려고 하는데, 리모컨의 온도 조절 버튼은 다음과 같다.

 

1) 온도를 1도 올리는 버튼

2) 온도를 1도 내리는 버튼

3) 온도를 5도 올리는 버튼

4) 온도를 5도 내리는 버튼

5) 온도를 10도 올리는 버튼

6) 온도를 10도 내리는 버튼

 

이와 같이 총 6개의 버튼으로 목표 온도를 조절해야 한다.

현재 설정 온도와 변경하고자하는 목표 온도가 주어지면 이 버튼들을 이용하여 목표 온도로 변경하고자 한다.

이 때 버튼 누름의 최소 횟수를 구하시오.

 

예를 들어, 7도에서 34도로 변경하는 경우,

7 -> 17 -> 27 -> 32 -> 33 -> 34

이렇게 총 5번 누르면 된다.

 

※ 입력

현재 온도a 와 목표 온도b가 입력된다. ( 0 <= a , b <= 40 )

 

※ 출력 

최소한의 버튼 사용으로 목표온도가 되는 버튼의 횟수를 출력한다.

# 리모컨
a, b = map(int, input().split())
c = abs(a-b)
count = 0

while c != 0:
    if c >= 10:
        c -= 10
        count += 1
    else:
        if c > 7:
            c += 1
            count += 1
        elif c > 4:
            c -= 5
            count += 1
        elif c > 2:
            c += 1
            count += 1
        else:
            c -= 1
            count += 1

print(count)

입력

7 34

 

출력 

5

 

[ 3310 ] 거스름돈

※ 문제

어떤 가게의 욕심쟁이 점원은 거스름돈을 나눠줄때 거스름돈의 개수를 적게해서 주고자 한다.

거스름돈을 입력 받아 점원이 줄 수 있는 최소 거스름돈의 개수를 출력하시오.

예를 들어 54520원인 경우,

거스름돈으로 50000원권 1장, 1000원권 4장, 500원 1개, 10원 2개 해서 총 8개이다.

(※ 현재 우리나라가 사용하고 있는 화폐를 사용한다. 10원 50원 100원 500원 1,000원 5,000원 10,000원 50,000원)

 

※ 입력

거스름돈 n이 입력된다. ( n은10이상의  int 범위 )

 

※ 출력 

최소 거스름돈의 개수를 출력한다.

# 거스름 돈
n = int(input())
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
array = [50000, 10000, 5000, 1000, 500, 100, 50, 10]

for coin in array:
    count += n // coin  # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기  // : 몫 연산자
    n %= coin  # % : 나머지 연산자

print(count)

입력

54520

 

출력 

8

 

[ 3321 ] 최고의 피자

※ 문제

vega 선생님은 Miss 피자 가게의 단골 손님이다.

그는 이번 달부터 절약 생활을 시작했다.

그래서 그는 피자 가게에서 주문할 수 있는 피자 중 1 달러 당 열량이 최대가 되는 피자를 주문하고 싶어한다.

이러한 피자를 "최고의 피자"라고 부르기로 하자.

"최고의 피자"는 1종류가 아니다.

Miss 피자는 N 종류의 토핑에서 여러 종류를 자유롭게 선택하여, 도우 위에 올려 주문할 수있다.

같은 토핑을 2 개 이상 올릴 수 없다.

도우에 토핑을 하나도 하지 않은  피자도 주문할 수있다.

도우의 가격은 A 달러이며, 토핑의 가격은 모두 B 달러이다.

실제 피자 가격은 도우의 가격과 토핑 가격의 합계이다.

즉, 토핑을 k 종류 (0 ≦ k ≦ N) 한 피자의 가격은 A + k × B 원이다.

피자 전체의 칼로리는 도우 열량과 토핑 칼로리의 합계이다.

도우의 가격과 토핑의 가격, 그리고 도우와 각 토핑 열량 값이 주어 졌을 때, "최고의 피자"의 1 달러 당 열량의 수를 구하는 프로그램을 작성하시오.

 

※ 입력

첫 번째 줄에는 토핑 종류 수를 나타내는 하나의 정수 N (1 ≦ N ≦ 100)이 입력된다.

두 번째 줄에는 두 개의 정수 A, B (1 ≦ A ≦ 1000,1 ≦ B ≦ 1000)가 공백을 구분으로 입력된다. A는 도우의 가격, B는 토핑의 가격을 나타낸다.

세 번째 줄에는 도우의 칼로리를 나타내는 정수 C (1 ≦ C ≦ 10000)가 입력된다.

3 + i 행 (1 ≦ i ≦ N)는 i 번째의 토핑 칼로리 수를 나타내는 정수 Di (1 ≦ Di ≦ 10,000)가 입력된다.

 

※ 출력 

"최고의 피자" 1 달러 당 열량의 수를 소수점 이하는 버리고 정수로 출력한다.

# 최고의 피자
import math
n = int(input()) # 토핑 종류 수
a, b = map(int, input().split()) # a: 도우 가격, b : 토핑 가격
c = int(input()) # 도우 칼로리
array = []
kal_array = []

for i in range(n):
    m = int(input())
    array.append(m)

array.sort()
array.reverse()

pizza = c / a
kal = c
k = 0

for i in array:
    c += i
    k += 1
    result = c/(a+(b*k))
    if pizza <= result:
        pizza = result
    else:
        break

print(math.trunc(pizza))

입력

3

12 2

200

50

300

100

 

출력 

37