백준 12034 김인천씨의 식료품가게 (Large)

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

12034번: 김인천씨의 식료품가게 (Large)

문제 해설

2N개의 가격표를 순회하며 정확히 75% 할인된 가격만 뽑아내 출력하는 문제다.

 

이 경우 map이나 set은 중복을 없애기 때문에 이용할 수 없다.

multimap이나 multiset은 가능하다.

 

본인은 인덱스를 통한 접근이 유용할 것 같아서 vector로 해결했다.

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <set>
#include <vector>
int main(){
    fio;
    int T; cin >> T;
    for(int t = 1; t<= T; t++){
        int N; cin >> N;
        vector<int> cost;
        for(int i=0; i <2*N; i++){
            int tmp; cin >> tmp;
            cost.push_back(tmp);
        }

        vector<int> ans;
        for(int i=0; i<cost.size(); i++){
            int now = cost[i];
            if(now == 0) continue;
            int origin = now/3;
            origin *= 4;
            for(int j=i+1; j<cost.size(); j++){
                if(cost[j] == origin){
                    ans.push_back(now);
                    cost[j] = 0;
                    break;
                }
            }
        }
        //
        cout <<"Case #"<<t<<": ";
        for(auto i:ans){
            cout << i <<' ';
        }
        cout <<'\n';
    }
    return 0;
}