[백준/c++] BOJ 1246 - 온라인 판매

https://www.acmicpc.net/problem/1246 

1246번: 온라인 판매

 

문제 설명

총 N개의 달걀이 있고, 잠재적인 고객은 총 M명이다. 그리고 각각의 i번째 고객은 각자 달걀 하나를 Pi 가격 이하로 살 수 있다고 밝혔다. 한 고객에게 두 개 이상의 달걀을 팔지 않기로 한다.

최대 수익을 올릴 수 있는 달걀의 가장 낮은 가격을 책정한다.

N, M (1 <= N, M <= 1000)

Pi (1 <= Pi <= 1,000,000)

해결

손님이 생각한 가격들을 벡터에 받아 정렬한다.

첫 가격을 제일 비싼 가격을 기준으로 잡고, 모든 가격을 돌면서 수익을 계산한다.

그 중, 수익이 가장 큰 가격과, 수익을 저장하고 출력하면 된다. 

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;
vector<int> v;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}

	sort(v.begin(), v.end());
	int ans = v[m - 1], ans2 = v[m - 1];
	for (int i = m - 2, idx = 2; i >= 0; i--, idx++) {
		if (ans2 <= v[i] * idx && n >= idx) {
			ans = v[i];
			ans2 = v[i] * idx;
		}
	}
	cout << ans << " " << ans2;
}