[백준] 5545번 최고의 피자

문제

상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 있는 피자 중 1원당 열량이 가장 높은 피자를 말한다. 최고의 피자는 여러 종류가 있을 수도 있다.

이 피자 가게는 토핑 N개에서 여러 종류를 선택해서 주문할 수 있다. 같은 종류의 토핑을 2개 이상 선택할 수는 없다. 또, 토핑을 전혀 선택하지 않을 수도 있다.

선택한 토핑은 도우 위에 올라간다. 도우의 가격은 A원이고, 토핑의 가격은 모두 B원이다. 피자의 가격은 도우와 토핑의 가격의 합계가 된다. 즉, 토핑을 k종류 (0 ≤ k ≤ N) 선택했다면, 피자의 가격은 A + B*k원이 된다. 피자의 열량은 도우와 토핑의 열량의 합이다.

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

입력

첫째 줄에 토핑의 종류의 수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 도우의 가격 A와 토핑의 가격 B가 주어진다. (1 ≤ A, B ≤ 1000) 셋째 줄에는 도우의 열량 C가 주어진다. (1 ≤ C ≤ 10000) 다음 줄부터 N개 줄에는 각 토핑의 열량 Di가 한 줄에 하나씩 주어진다. (1 ≤ Di ≤ 10000)

출력

첫째 줄에 최고의 피자의 1원 당 열량을 출력한다. 소수점 이하는 버리고 정수 값으로 출력한다.

 

요즘 그리디 문제를 푸는데... 자꾸 그리디랑 브루트랑 햇갈린다.ㅜㅜ

뭐,., 풀이가 햇갈리는게 아니니까... 

 

 

 

나는 이 문제를 부루트 포스 방식 + 그때 고를 수 있는 가장 큰 토핑의 가격을 더하는 아이디어를 접목시켰다.

#include <bits/stdc++.h>
using namespace std;

  int toppings[10001];
  
  int setTopping(int index, int cnt,int k, int sum) {
    if (cnt == k) {
      return sum;
    }
    return setTopping(index-1,cnt+1,k,sum + toppings[index]);
  }
  int main(void) {    
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 

    int n,k;
    cin >> n;

    int A,B;
    cin >> A >> B;

    int C;
    cin >> C;



    for(int i = 0; i<n;i++) {
      int to;
      cin >> to;
      toppings[i] = to;
    }

    k=n+1;
    sort(toppings, toppings+n);

    int mn = -1;
    while(k--) {
    int result = A+B  * k;
    int sum = setTopping(n-1,0,k,0) + C;
    mn = max(mn, sum/result);
    }

    cout << mn;


  }

개인적으로 파라미터를 return시키는 형태를 굉장히 많이 이용한다. 생각보다 괜찮은 것 같다.

 

토핑을 더하는 부분이 조금 지저분할 수 있는데

n-1은 토핑배열의 전체 길이에서 1을 뺀값인데... length()가 안 먹혀서 그냥 n으로 했다. c++에서 안된다는 이야기는 아니고... 그냥 하기 귀찮아서.ㅜㅜㅎㅎ

또 옆에 숫자 0이 있는데 이건 마지막 길이에서 하나 씩 뺄려고 했는데 그럴려고 보니 ..

중간에 걸리는 게 마음에 들지 않았다. 그렇다고 필요없는 초기값까지 갈 이유는 전혀 없다.

이것 또한 방법이 있을 수 있는데 그냥 k까지 가게 하면 좀더 편하게 할 수 있지 않을 까 해서 0부터 넣었다.

 

 

 

 

자 정리 해보면

 

내가 사용했던 아이디어는

 

1. 브루트 포스 방식을 이용한다.

2. 오름 차순으로 정렬하고, 가장 큰 수 부터 지정된 번호까지 토핑들의 가격들을 더해주면 된다.

 

 

이 두 아이디어를 필두로 코드를 작성하였다.

 

주의 할점은 k = n+1을 꼭 해줘야 한다.

왜냐하면 토핑을 사용하지 않는 경우도 있기 때문이다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, p, q, r, a[1005];

int main(){
	cin >> n >> p >> q >> r;
	for(int i=1; i<=n; i++) cin >> a[i];
	sort(a+1, a+n+1);
	reverse(a+1, a+n+1);
	int sum = r;
	int ret = 0;
	for(int i=0; i<n; i++){
		sum += a[i];
		ret = max(ret, sum / (p + q * i));
	}
	cout << ret;
}

 

흠.. 리버스 이건 생각못했는데.. 

 

리버스라...

.... 겁나 간단하군.... 나 뭐 한거지...