[C언어 / C++] 백준 | 1700번 멀티탭 스케줄링 반례 + 풀이 공유

1700번: 멀티탭 스케줄링

두 가지 경우로 나눠서 그리디하게 풀 수 있습니다.

 

1. 현재 꽂혀있는 플러그 중 나중에 쓰이지 않는 플러그가 있는 경우, 그 플러그를 뽑고 새로운 플러그를 꽂아주면 됩니다.

2. 현재 꽂혀있는 플러그 전부 나중에 쓰일 일이 있다면, 제일 등장 순서가 늦은 플러그를 뽑아주면 됩니다. 

 

밑에 자세히 설명해두었습니다.

 

ex) 

2 7

2 3 1 2 3 2 2 의 경우

2 3 플러그를 먼저 꽂은 후, 1을 꽂기 위해서 하나를 뽑아야 하는데, 그 뒤의 플러그 등장 순서를 보면 2 -> 3으로 3이 현재 꽂혀있는 플러그 중 등장순서가 가장 늦기 때문에 3번 플러그를 뽑아주면 됩니다.

 

생각하기도 쉽고, 반례도 딱히 없는 문제이지만 구현이 힘들었습니다.

반례 

2 7

2 3 1 2 3 2 2

OUTPUT : 2

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int main() {
int count = 0, c = 0,temp = -1, n, m, check[1000] = {}, arr[1000] = {}, plug[1000] = {}, index[1000] = {};
bool already = 0;
scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", &arr[i]);
    }
        for(int j = 0; j < m; j++) {
            if(plug[arr[j]] == 1) continue;
            else {
                plug[arr[j]] = 1;
                count++;
            }
            if(count == n) {
                temp = j;
                break;
            }
        }
    int later, none;
    for(int i = temp + 1; i < m; i++) {
        int zero = 0;
        for(int j = 0; j <= m; j++) {
            check[j] = 0;
            index[j] = 0;
        }
        later = 0, none = 0;
        already = 0;
        if(plug[arr[i]]) {
            already = 1;
        }
        if(already == 0) {
            for(int j = i + 1; j < m; j++) {
                if(plug[arr[j]] == 1) {
                    later = arr[j];
                    if(index[arr[j]] == 0) {
                        index[arr[j]] = ++zero;
                    }
                }  
                if(check[arr[j]] == 0 && plug[arr[j]] == 1) {
                    check[arr[j]] = 1;
                }
            }
            for(int j = 0; j < m; j++) {
                if(plug[arr[j]] == 1 && check[arr[j]] == 0) {
                    none = arr[j];
                    break;
                }
            }
            if(none) {
                c++;
                plug[none] = 0;
                plug[arr[i]] = 1;
            }
            else if(later) {
                for(int j = 0; j <= m; j++) {
                    if(index[j] == zero) {
                        later = j;
                        break;
                    }
                }
                c++;
                plug[later] = 0;
                plug[arr[i]] = 1;
            }
        }
       
    }
    printf("%d", c);
}