[백준 1246번] 온라인 판매 (C++)

문제링크 : https://www.acmicpc.net/problem/1246

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, M, arr[1001];

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

    cin >> N >> M;

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

    sort(arr, arr+M);;

    int tmp = 0;
    int idx = 0;

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

    cout << arr[M-idx] << "\n" << tmp;

    return 0;
}

 

먼저 입력받은 금액에 대해서 정렬을 해준다.

정렬된 값을 기준으로 가장 큰 값부터 현재 인덱스를 기준으로 가장 큰 값을 찾아간다.

 

물품을 2번 이상 사는 것은 불가능하므로, 최대 탐색 범위는 N, M 중 더 작은 값이다.

기본 정렬에 따라 오름차순으로 정렬된 상태이므로 맨 뒤의 값부터 차례로 값을 탐색한다.

 

그리고 해당 하는 값에 따른 가능한 i 수치를 곱해준다.

맨뒤의 값의 경우 자신보다 큰 값이 없기에 (i=1)번만 가능하다.

위치가 조정됨에 따라 해당 i 값을 곱하여 이렇게 곱한 값의 수치가 가장 클 때의 값과 idx 값을 저장하여 출력해주면 된다.