Approach 이 문제를 보고 파블로프의 개처럼 최댓값과 최솟값을 다루는 문제이므로 우선순위 큐를 생각할 수 있으나 잘 생각해보면 비효율적이라는 것을 쉽게 알 수 있다. 우선순위 큐를 활용한 접근 방법의 가장 큰 문제점은 최대힙과 최소힙이 서로 동기화가 안된다는 것이다. 즉 최대힙을 통해 지운 데이터가 최소합에 반영되기가 힘들다. 이 문제점을 해결하기 위해서 Map이나 Set 등의 자료구조등을 활용해서 지운 데이터인지를 계속해서 비교하는 방법등을 활용할 수 있으나 비효율적이다. 잘 생각해보면 Multiset은 order가 이미 힙트리 상에 저장되어있다. 즉, 이를 활용해주면 하나의 자료구조로 두 개의 값을 동시에 다룰 수 있는 장점이 있다. Codes Priority_queue를 활용한 방법 #incl..

접근 방법 일단, 어차피 카드 묶음이 1개씩 지워지는 상황이므로 무조건 큰 숫자가 나중에 묶이는 것이 유리하다. 그렇지 않으면 반복해서 묶이게 되어 숫자가 더 커지기 때문이다. 따라서, 숫자가 작은 것을 먼저 선택하기 위한 자료 구조가 필요하므로 우선순위 큐 자료구조를 활용해주면 된다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int n; cin >> n; priority_queue pq; for(int i = 0; i > temp; pq.push(temp); } int res..

접근 방법 우선순위 큐에 N만큼의 크기를 유지시키면서 pq의 최솟값을 갱신시켜주면 결과적으로 전체 세트의 N번째 최댓값을 쉽게 구할 수 있다. Priority queue 사용 느낌에 대해서 다시 한번 정리하는 용도로 정리해주면 된다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int n; cin >> n; priority_queue pq; for(int i = 0; i > temp; if(pq.size() < n) pq.push(..

문제 상황을 파악하기 위해서 여러번 시뮬레이션 하다보면 기존의 Amart 위치에 Imart를 짓는 것이 가장 유리하다는 것을 파악할 수 있다. 이때 우선적으로 선택되는 Imart의 위치는 다음과 같다. 예를 들어 Amart가 1 3 5위치에 놓여있다고 하자. 만약 3번을 선택했을 때 얻을 수 있는 사람의 수는 (1~3 사이의 사람의 수 / 2 + 1~3사이의 사람의 수 % 2) + 자기자신 + (3~5 사이의 사람의 수 / 2 + 3~5 사이의 사람의 수 / 2)라는 것을 파악할 수 있다. (단, alpha는 0 or 1) Amart 사이에 Imart가 놓이게 될 경우, 거리가 더 가까운 위치의 mart를 가게 되므로 사이의 위치한 사람의 수 / 2가 골라지는 것은 자명하다. 다만, 추가적으로 modul..

문제를 보고 생각보다는 쉽게 그리디 문제임을 파악할 수 있다. 문제 조건을 잘 보면, 최대한 많은 시민이 마스크를 구매할 수 있도록 유도해야한다. 즉 상식적으로 이 워딩을 보면 모든 시민들이 구매할 수 있게끔 최적(?)의 방법으로 구매하는 것이 가장 이득이라는 것을 간파할 수 있다. 즉, 이 지점에서 그리디 문제가 아닐까 의심을 해볼 수 있다. 직관적으로 잘 생각해보면 마스크를 제일 많이 팔 수 있는 경우는 해당 마스크 가격에만 구매할 수 있는 사람을 최우선적으로 구매권을 주면 된다는 것을 간파할 수 있다. 즉, 이 문제를 풀기 위해서는 각 상점을 기준으로 해당 가격 마스크를 시민들의 구매할 수 있는지 여부를 체크하고 그 중 가장 최적의 케이스 순서대로 구매를 진행해야 한다. 다만, 이 문제에서 입력값이..