문제 설명
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 달러 당 열량의 수를 소수점 이하는 버리고 정수로 출력한다.
입력 예시
3
12 2
200
50
300
100
출력 예시
37
문제 풀이
전체 코드
import math
array = []
topingCnt = int(input())
douPrice, topingPrice= map(int, input().split())
douCalories = int(input())
for i in range(topingCnt):
array.append(int(input()))
# 토핑을 하나씩 더하면서 평균이 가장 높은 값을 출력해줌.
array.sort(reverse=True)
avg = douCalories / douPrice
calories = douCalories
coast = 0
for j in array:
calories += j
coast += topingPrice
totalPrice = douPrice + coast
compAvg = calories / totalPrice
if compAvg > avg:
avg = compAvg
print(math.trunc(avg))탐욕법을 이용해 가격당 칼로리가 가장 높은 수를 구하는 문제이다.
단순하게 생각하면 토핑을 더하면서 평균값을 구하다가 가장 큰 평균값이 나오면 해당 값을 출력해주면 되는 문제이다.
여기서 중요한 것은 토핑의 칼로리 배열이다. 문제에서는 토핑은 무조건 중복으로 올릴 수 없으며, 토핑이 없는 경우도 있다고 한다.
그럼 배열로 받은 토핑을 하나씩 더하면서 평균값을 계속 계산해주면 되는 것이다.
대신 배열로 받은 칼로리의 정렬이 한번 필요하다. 거스름돈 문제를 생각해보자. 가장 높은 수 부터 차례대로 내려가면서 거스름돈을 구했었다.
이 문제도 마찬가지이다. 칼로리를 가장 높은 값부터 가져와 더하면서 평균값을 계산해주면 되는 것이다.
array.sort(reverse=True)여기서 array 는 토핑 칼로기가 들어가있는 배열리다. 위와 같이 역순 정렬을 한 후 계산을 해주면 된다.
처음 풀이는 아래와 같이 최초일 경우 토핑이 아무것도 없을때의 평균값을 먼저 구하고, 그 이후에 토핑을 하나씩 더하면서 평균을 구해주었다.
avg = 0.0
calories = douCalories
for j in range(topingCnt + 1):
if j == topingCnt:
break
# j가 1일 경우부터 토핑을 가져와서 계산.
if j != 0:
calories += array[j-1]
totalPrice = douPrice + topingPrice * j
compAvg = calories / totalPrice
# 가장 높은 평균을 avg 변수에 담는다.
if compAvg > avg:
avg = compAvg
# 소수점 이하 버리고 출력
print(math.trunc(avg))리팩토링 후에는 아예 처음 평균을 도우 평균으로 잡았다(토핑이 없을 경우 이 값으로 출력하기 위해). 그 후 반복문 안에서는 그냥 칼로리 값을 바로 가져와서 처리하도록 수정하였다.
avg = douCalories / douPrice
calories = douCalories
coast = 0
for j in array:
calories += j
coast += topingPrice
totalPrice = douPrice + coast
compAvg = calories / totalPrice
if compAvg > avg:
avg = compAvg
print(math.trunc(avg))문제 회고
탐욕법 문제에 조금씩 익숙해지는 듯 하면서도... 아직은 문제를 보면 머리가 하얘지는거 같다.
이번 문제는 처음에 봤을때는 어떻게 풀어야 할지 약간 막막했었다. 하지만 내가 어떤걸 구해야할지 명확하게 하고 나서 부터는 어떻게 접근해야 할지 조금은 감이 잡히는 느낌이었다. 이번 문제는 문제를 꼼꼼히 다시 읽고 나서 든 생각이
토핑을 하나씩 더하면서 평균이 가장 높은 값을 출력해줌.
이 생각이 퍼뜩 들었다. 그래서 해당 내용을 주석으로 바로 작성해주고 천천히 어떻게 구해봐야 할지 고민을 해봤다.
일단 토핑이 없을때는 예외로 두고, 토핑을 하나씩 더하면서 평균을 구해주려면 가장 큰 칼로리부터 더하면서 내려가면 되지 않을까 생각했다.
그래서 일단 받아온 칼로리 배열부터 역순 정렬로 큰 수부터 앞에 오게 정렬했으며, 해당 칼로리를 하나씩 더하면서 평균을 구할 수 있게 반복문에 평균을 구하는 공식을 그대로 넣어주었다. 그리고 반복문 마지막에는 가장 큰 평균만 변수에 담을 수 있도록 코드를 추가해주었다.
지금 한 3~4문제 정도 풀었는데, 탐욕법 문제들의 공통점이 일단 큰 수 부터 하나씩 내려가면서 계산하는 것 같다.
다음 문제도 이 부분을 좀 더 신경 써서 풀어봐야 할거 같다.
