[백준/C++] 1700번 멀티탭 스케줄링

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

이 문제 상당히 까다로운데, 풀이법은 다음과 같다.

​

1. 중복된 것이 꽂혀있다면 아무것도 하지 않는다.

2. 아무것도 안 꽂혀있다면 하나 꽂아준다.

3. 바꿔야할 전자기기의 다음 순서부터 탐색을 하는데, 멀티탭에 꽂혀있는 것들 중에서 가장 나중에 다시 등장하는 기기를 뽑아주면 된다!

​

1, 2번은 코드 이해에 크게 무리가 없으리라 생각하고 3번에 대해서만 자세히 설명하도록 하겠다.

cnt++;
        int dist=-1,loc;
        for (int j = 1; j <= n; j++) {
            int re_idx = 0;
            for (int z = i + 1; z <= k; z++) {
                if (plug[j] == elec[z]) break; // 뒤에 같은게 있다면 break
                re_idx++;
            }
            if (re_idx > dist) { // 제일 뒤에 다시 나오는 놈을 변경
                // idx를 계속 ++ 하기 때문에 아예 안나오는 놈이 제일 큰 값을 가짐
                dist = re_idx;
                loc = j;
            }
        }
        plug[loc]=elec[i]; // 변경

바꿔야할 전자기기의 다음 순서(= elec[z+1])부터 탐색을 시작하는데, plug[j]가 의미하는 전자기기와 같은 전자기기를 만날 때 까지 re_idx 변수를 1씩 증가시켜준다.

(같은 전자기기가 없다면 어떻게 될까? 뒤에서 마저 설명하겠다.)

re_idx와 dist 변수를 비교하여 re_idx (= 같은 전자기기가 있는 곳까지의 거리)가 dist보다 더 크다면, dist를 re_idx값으로 업데이트해주고, 바꿔야할 위치를 저장하는 변수인 loc을 현재 멀티탭에 꽂혀있는 전자기기의 위치를 나타내는 변수 j로 업데이트한다.

=> 멀티탭을 탐색하면서 자신과 동일한 전자기기가 제일 나중에 나오는 놈을 찾는 과정이다.

그리고 제일 나중에 나오는 놈을 뽑고 elec[i], 즉 새로 꽂아줘야할 놈을 꽂아주면 되는 것!

plug[j]가 의미하는 전자기기와 같은 전자기기가 뒤에 등장하지 않는다면, idx값은 z<=k일 때 까지 증가하면서 자연스레 제일 큰 값을 가지게 될 것이고, 그렇게 된다면 역시 자연스레 아예 등장하지 않는 놈이 변경될 것이다.

#include <bits/stdc++.h>

using namespace std;

int elec[101]; // k
int plug[101]; // n

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n,k,cnt=0;
    bool flag;
    cin >> n >> k;
    for(int i=1; i<=k;i++){
        cin >> elec[i];
    }
    for(int i=1; i<=k;i++) {

        // 1번. 만약 같은게 꽂혀있다면 패스
        flag = false;
        for (int j = 1; j <= n; j++) {
            if (elec[i] == plug[j]) {
                flag = true;
                break;
            }
        }
        if (flag) continue;

        // 2번. 빈 구멍에 하나 꽂기
        for(int j=1; j<=n ;j++){
            if(plug[j]==0){
                plug[j]=elec[i];
                flag=true;
                break;
            }
        }
        if (flag) continue;

        // 3. 바꿔야 한다면
        cnt++;
        int dist=-1,loc;
        for (int j = 1; j <= n; j++) {
            int re_idx = 0;
            for (int z = i + 1; z <= k; z++) {
                if (plug[j] == elec[z]) break; // 뒤에 같은게 있다면 break
                re_idx++;
            }
            if (re_idx > dist) { // 제일 뒤에 다시 나오는 놈을 변경
                // idx를 계속 ++ 하기 때문에 아예 안나오는 놈이 제일 큰 값을 가짐
                dist = re_idx;
                loc = j;
            }
        }
        plug[loc]=elec[i];
    }
    cout << cnt;
    return 0;
}

반례

3 5

1 1 1 1 2

ans : 0

​

2 10

1 1 2 1 1 2 1 1 2 1

ans : 0

​

3 14

1 4 3 2 5 4 3 2 5 3 4 2 3 4

ans: 4