• Home
  • About
    • 코드좀비 photo

      코드좀비

      An amazing website.

    • Learn More
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[BOJ] 백준 17274 카드 공장(Large) c++ 실패...

10 Jun 2019

Reading time ~1 minute

코드

#include <map>
#include <queue>
#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
	int m, n;
	int geta, getb, middle;
	long long int result = 0;
	multimap<int, int> cards;
	queue<pair<int, int>> save;

	scanf(" %d %d", &m, &n);
	for (int i = 0; i < m; i++) {
		scanf(" %d %d ", &geta, &getb);
		cards.insert(make_pair(geta, getb));
	}
	for (int i = 0; i < n; i++) {
		scanf(" %d", &middle);
		auto iter = cards.begin();
		
		while (iter->first <= middle) {
			if (iter->second <= middle) {
				save.push(make_pair(iter->first, iter->second));
				
			}
			else {
				cards.insert(make_pair(iter->second, iter->first));
			}
			iter++;
			cards.erase(cards.begin());

			if (iter == cards.end())
				break;
		}
		while (!save.empty()) {
			cards.insert(make_pair(save.front().second, save.front().first));
			save.pop();
		}
	}
	
	for (auto iter = cards.begin(); iter != cards.end(); iter++) {
		result += iter->first;
	}
	
	cout << result;
	cin >> result;

	return 0;
}

주저리

도대체 어떻게 짜야 하는 걸까…

자료의 스왑 시간과, 탐색 시간을 줄이기 위해서

멀티맵을 사용하였다.

이거보다 직접 뒤집는걸 시뮬레이션 했을떄 더 빠른 방법은 생각이 나질 않는다..

오늘 안에 도저히 풀어 올리는게 불가능하다고 생각이 되어

내일 이나 언제든 다시 도전 해보려고 한다..

지금 제일 최적으로 떠오르는 대안은

앞면카드[]

뒷면카드[]

앞뒤포인터[]

이런식으로 하나하나 다 대조하는거 뿐…

맵도 시간초과가 났는데 이게 가능 할지는 모르겠다.

특이한 케이스 ( 예를 들자면 매번 마다 다 뒤집히는 바람에 큐에 넣고 빼는일이 많아지는경우)

를 제외하면 도저히 시간 초과 날 이유는 없어보인다.


6월11일 오늘도 실패해서 과거 업로드 했던걸 끌어서 올렸다..

마치 웹툰 작가가 세이브 원고를 묵혀두고 처리하느는낌?

우선 priority_queue 를 사용해서 해보는게 가장 좋을 거 같다.



백준시뮬레이션simulationC++multimap Share Tweet +1