📝 문제 정보#
🧐 관찰 및 접근#
- 그리디하게, 뽑아야할때 곧 쓸만한걸 남기고, 나중에 쓸만한걸 뽑으면 되지 않을까?
- 증명해보자.
- 현재 $N$개의 구멍이 꽉차있고, $A$를 새로 꽂아야한다고 가정하자.
- 가장 나중에 쓰는걸 뽑는 전략 $G$가 있고, 어떤 최적의 전략 $Opt$가 있다고 가정하자.
- 이제 $G$가 $Opt$보다 나쁘지 않음을 보이면 된다.
- 어느 순간, $A$를 꽂기 위해 $G$는 $X$를, $Opt$는 $Y$를 뽑았다.
- 이때, 이후에 $X$가 먼저 등장한다면, $G$는 한번 더 뽑/꼽을 수행해야하고, $Opt$는 아니다.
- $Y$가 먼저 등장했다면, $Opt$는 뽑/꼽을 수행해야 하고, $G$는 아니다.
- 그런데, $G$의 전략 특성상 $Y$보다 $X$가 늦게 등장해야하므로, 언제나 $Opt$보다 $G$가 나쁘지 않다.
💻 풀이#
- 코드 (C++):
void solve(){
int N, K; cin >> N >> K;
vector<queue<int>> nxt(K+1);
vector<int> A(K);
rep(i, 0, K) cin >> A[i];
rep(i, 0, K) nxt[A[i]].push(i);
rep(i, 1, K+1) nxt[i].push(1e9);
set<pii> st; // (nxt use, val)
vector<bool> inuse(K+1, false);
int ans = 0;
rep(i, 0, K){
int val = A[i];
if(inuse[val]){ // 이미 꽂혀있다면
st.erase({i, val});
}
// 꽂혀있지 않다면
else if((int)st.size() < N){ // 남은 자리가 있으면
inuse[val] = true;
}
else{ // 남은 자리가 없으면
ans++;
pii old = *st.rbegin();
st.erase(old);
inuse[old.second] = false;
inuse[val] = true;
}
nxt[val].pop();
if(!nxt[val].empty()) st.insert({nxt[val].front(), val});
}
cout << ans << '\n';
}