[Greedy] 1700번 멀티탭 스케줄링

1700번 멀티탭 스케줄링

 

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

 

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

 

입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.

 

출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

 

예제 입력

2 7
2 3 2 3 1 2 7

3 9
1 2 3 4 2 1 3 3 2

2 15
3 2 1 2 1 2 1 2 1 3 3 3 3 3 3

 

예제 출력

2

2

2

 

해결방법

Greedy Algorithm 유형의 문제이다

시간이 정말 오래 걸린 문제인데 약간 하드코딩이다 보니 반례를 찾고 분석하는데 너무 많은 시간이 걸렸다.... 😭😭

 

 

⭐️ 솔루션 ⭐️

콘센트를 빼야한다면 ??

멀티탭에 연결되어있는 전자용품 중에서 추후에 사용이 가장 늦는 (혹은 앞으로 사용하지 않을) 콘센트를 빼고 새로운 콘센트를 연결해야한다

 

전체적인 흐름은 아래와 같다

1. 사용할 순서대로 전자용품을 탐색한다
2. 먼저 이미 콘센트가 꽂혀있다면 그대로 사용한다
3. 만약 콘센트가 꽂혀있지 않은데, 빈 콘센트가 존재한다면 해당 자리에 연결한다
4. 반대로 빈 콘센트가 존재하지 않는다면 기존의 연결된 콘센트 중 하나를 뽑아야한다
5. 추후에 사용할 계획이 없다면 해당 콘텐트를 뽑고, 만약 전체 용품이 추후에 사용된다면 그 중 가장 늦게 사용하는 콘센트를 뽑고 새로운 전자용품을 연결시킨다

 

최적해와 그리디 알고리즘

위와 같은 논리는 현재를 기준으로 처음 사용하는 시점이 가장 늦은 것을 찾는 것이 항상 최적이기 때문에 그리디 알고리즘을 사용하여 문제를 해결할 수 있다

 

시간 복잡도

모든 전자용품 K개 에 대해 탐색을 하며, n개 의 멀티탭의 용품을 K개 의 전자용품 사용순서만큼 탐색하므로 시간복잡도는 O(n*k^2) 을 가지게 된다

 

 

 

소스코드

문제 해결 시간 : 2h 30m

메모리 : 1988 KB

시간 : 0 ms

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

int n,k,ans;
vector<int> order;

int multiTap[101];

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> k;
    for(int i=0; i<k; i++){
        int in;
        cin >> in;
        order.push_back(in);
    }
    
    ans = 0;
    
    for(int i=0; i<order.size(); i++){
        int item = order[i];
        
        // 이미 콘센트가 꽂혀있는가?
        bool found = false;
        for(int j=1; j<=n; j++){
            if(multiTap[j] == item){
                found = true;
                break;
            }
        }
        
        // 콘센트가 안꽂혀있다면
        if(!found){
            // 빈 콘센트가 존재한다면
            bool empty = false;
            for(int j=1; j<=n; j++){
                if(multiTap[j] == 0){
                    multiTap[j] = item;
                    empty = true;
                    break;
                }
            }
            
            // 빈 콘센트가 존재하지 않아 하나를 빼야한다면
            if(!empty){
                int ind = 0;
                int max_value = 0;
                bool reuse = true;
                
                // 멀티탭의 전기용품들을 탐색
                for(int j=1; j<=n; j++){
                    int cnt = 1;
                    bool end = true;
                    
                    for(int l=i; l<order.size(); l++,cnt++){
                        if(multiTap[j] == order[l]){
                            if(cnt > max_value){
                                max_value = cnt;
                                ind = j;
                            }
                            
                            // 해당 전기용품은 추후에 재사용됨
                            end = false;
                            break;
                        }
                    }
                    
                    // 멀티텝의 물건들이 추후에 사용되지 않는 경우
                    if(end){
                        multiTap[j] = item;
                        ans++;
                        reuse = false;
                        break;
                    }
                }
                
                // 멀티탭의 물건들이 추후에 전부 사용되는 경우
                if(reuse){
                    multiTap[ind] = item;
                    ans++;
                }
            }
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}