BOJ 1713 후보 추천하기

사용한 알고리즘

구현

알고리즘 설명

사진틀의 개수가 적으므로 O(N^2KlogN) 감당 가능하다.
먼저 사진을 담아둘 곳을 만든 뒤 모든 값을 0으로 설정한다.
사진틀을 내림차순으로 정렬하여 이미 기제된 사진틀을 먼저 볼 수 있도록 한다.
1. 사진이 이미 기제되어 있는 경우 추천수를 올린다.
1. 사진틀이 기제되지 않은 경우 새로운 사진을 추가하고 날짜를 기입한다.
위 두 경우가 아닌 경우 가장 추천수가 적으면서 오래된 사진(마지막 사진틀)를 제거하고 새로운 사진을 추가한다.
남은 포스터를 출력한다.

풀이

// baekjoon 1713 yechan
#include <cstdio>
#include <vector>
#include <utility>
#include <functional>
#include <algorithm>
using namespace std;
const int MAX_N=20;
const int MAX_NUM=101;

int N, K, x;
pair<pair<int, int>, int> poster[MAX_N]; // ((count, day), student Index)
vector<int> ans;

int main() {
	scanf("%d%d", &N, &K);
	for (int i=1; i<=K; i++) {
		scanf("%d", &x);
		sort(poster, poster+N, greater<pair<pair<int, int >, int> >());
		bool check=false;
		for (int j=0; j<N; j++) {
			if (poster[j].first.first == 0) {
				poster[j].first.first = 1; // count
				poster[j].first.second = i; // day
				poster[j].second = x; // index
				check = true;
				break;
			}
			if (poster[j].second == x) { // match index
				poster[j].first.first++; // count
				check = true;
				break;
			}
		}
		if (check) continue;
		poster[N-1].first.first = 1; // count
		poster[N-1].first.second = i; // day
		poster[N-1].second = x; // index
	}
	for (int i=0; i<N; i++) {
		if (poster[i].second) {
			ans.push_back(poster[i].second);
		}
	}
	sort(ans.begin(), ans.end());
	for (int i=0; i<ans.size(); i++)
		printf("%d ", ans[i]);
	puts("");
	return 0;
}