[BOJ / C++] #1700 멀티탭 스케쥴링

그리디 2문제만 더 풀고 잘라했는데
이 문제에서 잘못 생각해서 시간 순삭됐다 🥲.

문제 풀이

이 문제의 핵심은, 플러그를 뽑을 때

이후 한 번도 쓰이지 않을 기기거나, 제일 마지막에 쓰일 기기를 뽑는 것이다.

1. 사용 순서(K번)들을 order 배열에 받는다.
2. K번 반복문 돌기
   1. 현재 플러그에 꼽혀있나 -> 뽑을 필요 없이 continue
   2. 플러그가 비어있나 -> 빈 자리에 꽂은 후 continue
   3. 1,2번 둘 다 아님 -> 플러그를 뽑아야 한다.
      • 그리디 하게 접근!
      • 나머지 order에 있는 것 중에, 이후 한 번도 쓰이지 않는 것이나 제일 마지막에 쓰일 기기.

실수

1. 처음에 N-1개는 다 꽂을 수 있다 생각해서 꽂아버렸다.. 중복이 있을 수 있는데 ^^;
2. 그리디하게 뽑을 것을 찾을 때, 만약에 플러그에 2,1이 꽂아져 있고 남은 order가
   3, 2, 2, 1, 2 일 때 가장 나중에 쓰이는 것은 1이다..ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ ㅜ 2가 여러 번 있을 때 이후 가장 최근에 나올 걸로 따져야 하는데 제일 마지막에 쓰이는 거라고 생각하다보니깐 중복돼도 멈추지 않고 끝 인덱스까지 찾고있었다.

코드

#include <iostream>
using namespace std;

int cnt=0;
int N, K;
int order[101], plugs[101];

int main(){

    cin>>N>>K;

    for(int i=0;i<K;i++){
       cin>>order[i];
    }

    //사용횟수 <= 멀티탭 구멍 개수
    if(K<=N){
        cout<<0<<"\n";
        return 0;
    }

    //<실수1🥲> 0~N-1까지 그냥 넣으면 안 됨 . 거기서도 중복 있을 수 있음..

    for(int i=0;i<K;i++){
        bool isPlugged=false;
        //현재 플러그에 꼽혀있나
        for(int j=0;j<N;j++){
            if(order[i]==plugs[j]) {
                isPlugged=true;
                break;
            }
        }

        if(isPlugged) continue;


        // 비어있는지 확인
        for(int j=0;j<N;j++){
            if(!plugs[j]){
                plugs[j]=order[i];
                isPlugged=true;
                break;
            }
        }

        if(isPlugged) continue;


        // 현재 플러그에 없으면 뭘 뽑아야할지 골라야 함
        // 플러그에 있는 것중 가장 나중에 사용하는 것 제거 (또는 아예 사용되지 않는 것)
        int plugsIdx; //뽑을 플러그 인덱스
        int max=-1;

        for(int j=0;j<N;j++){
            int lastIdx=-1;
            for(int k=i+1;k<K;k++){
                if(plugs[j]==order[k]){
                    lastIdx=k;
                    break; // <실수1🥲> 중복되면 가장 최근에 쓰이는 걸로 찾아야됨....
                }
            }

            if(lastIdx==-1){ //사용된 적 없으면
                plugsIdx=j;
                break;
            }

            if(lastIdx>max){
                plugsIdx=j;
                max=lastIdx;
            }
        }
        //뽑기
        plugs[plugsIdx]=order[i];
        cnt++;
    }

    cout<<cnt<<"\n";
    return 0;
}

이제 자야지.