맛있는 사과 (BOJ 32963)

문제

이미지클릭

문제 설명

• i번의 사과의 맛: ti
• i번의 사과의 크기: si

q개의 질문이 정수 p의 형태로 들어온다.

1. 사과의 맛(ti) 이 p값 이상인 사과를 선택해 준다.
2. 여기에서 가장 큰 사과의 개수를 출력해 준다.

문제 해설

• 우선 사과의 맛(t)을 기준으로 내림 차순으로 정렬해 준다.

vector<pair<int, int>> apples;
for (int i = 0; i < n; i++) apples.push_back({t[i], s[i]});
sort(apples.begin(), apples.end(), greater<>());

• 그런 다음 질문 정수들도 {입력받은 정수, 입력받은 순서(인덱스)} 의 형태로 지정해 주고 입력받은 정수를 기준으로 내림 차순으로 정렬해 준다.

vector<int> ans(q);
vector<pair<int, int>> queries;
for (int i = 0; i < q; i++) {
     long long x; cin >> x;
     queries.push_back({x, i}); //입력 받은 정수, 입력받은 순서(인덱스)
}
sort(queries.begin(), queries.end(), greater<>());

입력받은 정수를 기준으로 정렬하는 이유는 다음과 같이 확인할 수 있다.

예제

5 5
1 3 2 4 5
3 2 3 2 1
1
2
3
4
5​

예제를 통해 확인한다면 apples에는 다음과 같이 저장이 될 것이다.

{5,1}, {4,2}, {3,2], {2,3}, {1,3} //apples

apples를 이렇게 저장을 해두었기 때문에 오프라인 쿼리를 통해서 탐색하기 위해서는 큰 선택한 정수가 큰 수를 기준으로 하여서 마치 그리디와 비슷하게 점령해 나가야 한다!

{5,5}, {4,4}, {3,3}, {2,2}, {1,1} //queries

이렇게 하게 된다면 apples와 queries에서도 볼 수 있듯이 차례대로 사과의 최대 크기를 구하고 개수를 산출해 낼 수 있다.

{5,5} queries
=>{5,1} apples 말고는 사과의 맛이 좋은 사과는 존재 안함! 
최대 크기 : 1, 개수 : 1

{3,3} queries
=>{5,1}, {4,2}, {3,2} 존재
최대 크기 : 2, 개수 : 2

최종 코드

#include<bits/stdc++.h>
using namespace std;
int n, q;
vector<long long> t, s;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        t.push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        s.push_back(x);
    }

    vector<pair<int, int>> apples;
    for (int i = 0; i < n; i++) apples.push_back({t[i], s[i]});
    sort(apples.begin(), apples.end(), greater<>());

    vector<int> ans(q);
    vector<pair<int, int>> queries;
    for (int i = 0; i < q; i++) {
        long long x; cin >> x;
        queries.push_back({x, i});
    }
    sort(queries.begin(), queries.end(), greater<>());

    long long j = 0, mx = 0, cnt = 0;
    for (int i = 0; i < q; i++) {
        int limit = queries[i].first, idx = queries[i].second;
        while (j < n && apples[j].first >= limit) {
            if(j==0) mx=apples[j].second, cnt=1;
            else{
                  if(mx<apples[j].second) mx=apples[j].second, cnt=1;
                  else if(mx==apples[j].second) cnt+=1;
            }
            j++;
        }
        ans[idx]=cnt;
    }

    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}

이미지클릭