https://www.acmicpc.net/problem/1700
이 문제는 처음에 그리디를 어떤 방식으로 짜는지가 문제 풀이의 핵심이다
처음에 나는 숫자가나온 갯수에 따라 그리디를 선택 했지만
1700 에서 사용하는 스케줄링 방식은 가장 오랫동안 안쓰는 원소를 교체하는 방식으로 그리디를 작성 한다
이에 큐를 사용하여 나오는 위치를 저장해주고 이를 이용해서 비교해줌으로서 값을 출력하는 방식을 사용했다
#include<iostream>
#include<queue>
using namespace std;
int n, k;
int arr[100];
int concent[100];
queue<int> useCount[101];
bool isUsed[100] = { 0, };
int main() {
int cnt = 0;
int input = 0;
cin >> n >> k;
for (int i = 0; i < k; i++) {
cin >> arr[i];
useCount[arr[i]].push(i);
}
int i = 0;
while (input < n && i < k) {
if (!isUsed[arr[i]]) {
isUsed[arr[i]] = true;
concent[input] = arr[i];
useCount[arr[i]].pop();
i++;
input++;
}
else {
useCount[arr[i]].pop();
i++;
}
}
if (n > k) {
cout << 0;
return 0;
}
else {
for (int j = i; j < k; j++) {
int willPlug = arr[j];
useCount[arr[j]].pop();
int outConcnet=-1;
int notUse=0;
bool isIn = false;
for (int l = 0; l < n; l++) {
if (concent[l] == willPlug) {
outConcnet = l;
isIn = true;
break;
}
}
if (!isIn) {
for (int l = 0; l < n; l++) {
if (useCount[concent[l]].empty()) {
outConcnet = l;
break;
}
if (notUse < useCount[concent[l]].front()) {
notUse = useCount[concent[l]].front();
outConcnet = l;
}
}
}
if (concent[outConcnet] != willPlug) {
concent[outConcnet] = willPlug;
cnt += 1;
}
}
}
cout << cnt;
}
'백준(코테준비) > 그리디' 카테고리의 다른 글
백준 3109 / c++ / 그리디 / dfs (0) | 2025.01.12 |
---|---|
백준 2212 / cpp / c++ (0) | 2024.12.17 |
백준 1092 / CPP (0) | 2024.12.01 |
백준 12904 (0) | 2024.08.09 |
백준 2812 / C++ (0) | 2024.08.03 |