취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1246번 문제인 온라인 판매이다.

문제는 아래 링크를 확인하자.

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

계란을 가장 비싸게 살 의향이 있는 i명에게 그중 가장 싸게 살 의향이 있는 사람의 가격으로 계란을 팔았을 때 얻는 이득들 중 가장 비싼 값을 구하는 것으로 충분하다. i명에게 더 저렴한 가격으로 계란을 팔면 손해뿐이기 때문이다.

이는 각 사람들이 사고자 하는 값인 Pi를 먼저 정렬해두는 것으로 빠르게 계산할 수 있다.

문제 조건에서, 최대 이익을 얻을 수 있는 계란의 가격 중 "최소"비용을 구하라고 한 점에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1000];

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

	int N, M; cin >> N >> M;
	for (int i = 0; i < M; i++) cin >> arr[i];

	sort(arr, arr + M);

	int ans = 0, idx = 0, k = min(N, M);
	for (int i = 1; i <= k; i++) {
		if (ans <= i * arr[M - i]) ans = i * arr[M - i], idx = i;
	}

	cout << arr[M - idx] << '\n' << ans;
}