[ 백준 1700 ] 멀티탭 스케줄링 (C++)

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

1700번: 멀티탭 스케줄링

 

문제를 읽고 'DFS로 풀면 되겠구나'라고 생각해서 무지성 코딩을 했는데 시간 초과가 났다. 반례들은 다 통과하기 때문에 정답을 도출하는 것에는 문제가 없는 코드라고 생각한다. 다만 모든 경우의 수를 따지기 때문에 비효율적일 뿐... 우선 버리기는 아까우니깐 DFS 코드를 살펴보자. 알고리즘은 아래와 같다. (정답 코드는 아래쪽에 있음)

 

함수 형태: void DFS(int input[], int idx, vector<int> v, count);
매개변수 설명
int input[]: 전자기기 순서 배열
int idx: input 배열의 인덱스
vector<int> v: 콘센트
count: 뽑은 횟수

1. input의 끝까지 도달하면 최소값(Min)에 min(Min, count) 저장
2. 콘센트에 전자기기가 이미 꽂혀 있으면 idx++ 해주고 DFS 호출
3. 콘센트에 빈 칸이 있으면 꽂아주고 idx++ 해주고 DFS 호출
4. 그 외의 경우 콘센트에 있는 전자기기를 하나씩 다 빼본다

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, K, tmp;
int Min = 100;

bool check(vector<int> v, int x){
    for(int elem : v){
        if(elem == x)
            return true;
    }
    return false;
}

void DFS(int input[], int idx, vector<int> v, int count){
    if(idx == K){
        Min = min(Min, count);
    }
    else if(check(v, input[idx])){
        DFS(input, idx + 1, v, count);
    }
    else if(v.size() < N){
        v.push_back(input[idx]);
        DFS(input, idx + 1, v, count);
    }
    else{
        for(int i = 0; i < v.size(); i++){
            tmp = v[i];
            v[i] = input[idx];
            DFS(input, idx + 1, v, count + 1);
            v[i] = tmp;
        }
    }
}

int main(){
    cin >> N >> K;
    int* input = new int[K];
    vector<int> v;
    
    for(int i = 0; i < K; i++){
        cin >> input[i];
    }
    
    DFS(input, 0, v, 0);
    
    cout << Min << endl;
    
    delete[] input;
    
    return 0;
}

 

이제 정답 코드를 살펴보자. 알고리즘은 정말 간단하지만 생각하기가 꽤나 까다로운 문제였던 거 같다. 방법이 떠오르면 풀만한 문제지만 그렇지 않으면 오래 걸리는 문제.. 아래의 규칙만 따르면 된다.

 

1. 콘센트에 이미 있으면 continue
2. 빈칸 있으면 빈칸에 꽂아주고 continue
3. else
    3-1. 다시 쓸 일 없는 콘센트 있으면 뽑아준다
    3-2. 꽂혀있는 것들 중 제일 마지막에 쓰일 기기 뽑는다

 

#include <iostream>
#include <vector>
using namespace std;

// x가 벡터 v 안에 있는지 검사
bool check(vector<int>& v, int x){
    for(int elem : v){
        if(elem == x)
            return true;
    }
    return false;
}

int main(){
    int N, K;
    int count = 0;
    
    cin >> N >> K;
    int* input = new int[K];
    int* ch_behind = new int[N];
    vector<int> outlet;
    for(int i = 0; i < K; i++){
        cin >> input[i];
    }

    for(int i = 0; i < K; i++){
        // 1. 콘센트에 이미 있으면 continue
        if(check(outlet, input[i]))
            continue;
        
        // 2. 빈칸 있으면 빈칸에 꽂아주고 continue
        if(outlet.size() != N){
            outlet.push_back(input[i]);
            continue;
        }
        
        int reuse = 0;
        // 3-1. 다시 쓸 일 없는 콘센트 있으면 뽑아준다
        for(int idx = 0; idx < N; idx++){
            reuse = 0;
            for(int j = i; j < K; j++){
                if(outlet[idx] == input[j]){
                    reuse++;
                }
            }
            if(reuse == 0){
                // 다시 사용하지 않으므로 뽑아준다
                outlet[idx] = input[i];
                count++;
                break;
            }
        }
        
        if(reuse == 0) continue;
        
        // ch_behind 모두 0으로 초기화;
        for(int idx = 0; idx < N; idx++)
            ch_behind[idx] = 0;
        
        int change_idx = 0;
        // 3-2. 제일 마지막에 쓰이는 기기 뽑는다
        for(int j = i; j < K; j++){
            for(int idx = 0; idx < N; idx++){
                if(ch_behind[idx] == 0 && outlet[idx] == input[j]){
                    change_idx = idx;
                    ch_behind[idx] = 1;
                }
            }
        }
        outlet[change_idx] = input[i];
        count++;
    }
    
    cout << count << endl;
   
    delete[] input;
    delete[] ch_behind;
    
    return 0;
}