백준 1700번: 멀티탭 스케줄링

문제 링크 : https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

 문제 설명 

 

멀티탭 구멍의 개수와 전기용품의 총 사용횟수가 주어지고

전기용품 이름이 사용순서대로 주어짐 이때 멀티탭에서 플러그를 최소한으로 빼는 경우의 수를 출력

 

 알고리즘 

 

1. 첫번째 전기용품은 플러그에 꼽고 그다음  플러그 의 크기만큼 전기용품을 꼽는데 , 이미 꼽혀있는 플러그는 꼽을 필     요가 없으니까 넘긴다.

2.  플러그가 모두 사용중일 때 앞으로 사용할 전기 제품중 가장 나중에 사용할제품이거나 사용하지 않을 제품의

    플러그를 빼고 다음 제품 코드를 꼽는다 .

 

 코드 

\

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main() {
    int N, K;
    int arr[101];
    vector<int>mult;
 
    cin >> N >> K;
 
    int result = 0;
 
 
    //플러그 사용 순서 입력
    for (int i = 0; i < K; i++) {
        cin >> arr[i];
    }
 
 
    //첫번째 사용 플러그 꼽기
    mult.push_back(arr[0]);
 
    for (int i = 1; i < K; i++) {
 
        //플러그가 모두 사용중
        if (mult.size() == N) {
 
            bool pos = false;
 
            for (int j = 0; j < N; j++) {
 
                //플러그가 이미 꼽혀있다.
                if (arr[i] == mult[j]) {
                    pos = true;
                }
            }
 
            if (pos == true)continue;
 
            //플러그가 꼽혀있지 않다.
            else {
 
                //플러그를 1회 뺴야되기때문에 result ++
                result++;
                vector<pair<int, int>>P;
 
                for (int j = 0; j < N; j++) {
                    //idx 최대값
                    int idx = 100;
 
                    //꼽혀있는 플러그들이 언제 사용할 것인지 찾는 과정
                    for (int k = i; k < K; k++) {
 
                        if (mult[j] == arr[k]) {
                            idx = k;
                            break;
                        }
 
                    }
 
                    P.push_back(make_pair(idx, mult[j]));
                }
 
                sort(P.begin(), P.end());
 
                for (int j = 0; j < N - 1; j++) {
                    //가장 나중에 사용할 제품 빼고는 안빼도 되니까 그대로 둔다.
                    mult[j] = P[j].second;
                }
                //새 전기제품 꼽기
                mult[N - 1] = arr[i];
 
            }
 
        }
 
        //멀티탭에 빈 자리가 있다.
        else {
 
            bool pass = false;
            for (int j = 0; j < mult.size(); j++) {
 
                //이미꼽혀있으면 pass
                if (arr[i] == mult[j]) {
                    pass = true;
                    break;
                }
 
            }
 
            //꼽혀잇지 않으면 꼽는다.
            if (!pass)mult.push_back(arr[i]);
 
        }
 
    }
    cout << result;
 
}