백준 1700 멀티탭 스케줄링 c++

알고리즘

그리디 알고리즘을 이용하여 풀 수 있는 문제였다.

자료구조

• 전자기기를 사용하는 순서가 중요하고 전자기기 이름이 전자기기 최대 사용 횟수 k개 이하의 자연수로 주어지기 때문에 입력값으로 받는 사용할 전자기기 이름을 int 배열에 저장한다.
• 사용할 전자기기 이름을 통해 사용유무를 bool 배열에 저장한다. 대신 멀티탭 사용 횟수가 n개로 제한되어 있기 때문에 cnt 변수로 멀티탭 사용 개수를 세어 사용을 제어한다.

구현

1. 입력값으로 받은 전자기기 배열을 순회한다.
2. 순회하면서 plug에 꽂은 전자기기라면 continue
3. plug에 꽂은 전자기기가 아닌데, plug에 자리가 있다면 true값주고 cnt++
4. plug에 꽂은 전자기기가 아니면서 plug에 자리가 없을 경우, plug에 꽂은 전자기기 중에서 가장 나중에 사용할 전자기기를 뽑고 그 자리에 새로운 전자기기를 꽂는다.

코드

#include <bits/stdc++.h>
using namespace std;

int a[103], ans, cnt;
bool power[103];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k; cin >> n >> k;
    for(int i = 1; i <= k; i++) cin >> a[i];
    
    // 입력값으로 받은 전자기기 이름 순회
    for(int i = 1; i <= k; i++) {
    	// cur이 전자기기 이름
        int cur = a[i];
        
        // 이미 plug에 꽂힌 전자기기면 continue
        if(power[cur]) continue;
        
        // plug에 없는데 plug 자리가 있으면 넣기
        if(cnt < n) {
            power[cur] = true;
            cnt++;
        }
        
        // power도 off고 plug도 자리가 없을 때, 대체자리 찾기
        // plug에 꽂힌 전자기기 중에서 가장 늦게 사용할 전자기기 선택해서 뽑기
        else {
            vector<pair<int, int>> v;
            for(int x = 1; x <= k; x++) {
            	// plug에 없는 전자기기는 패스
                if(!power[x]) continue;
                
                // cur 이후의 전자기기 중에서 가장 먼저 사용하는 전자기기가 있다면 
                // 전자기기 index와 전자기기 이름 저장하기
                bool vis = false;
                for(int y = i+1; y <= k; y++) {
                    if(a[y] == x) {
                        v.push_back({y, x});
                        vis = true;
                        break;
                    }
                }
                // 없으면 이후에 사용하지 않을 전자기기이기 때문에 index를 가장 큰 값으로 해준다.
                if(!vis) v.push_back({k+1, x});
            }
            // 내림차순으로 sort
            sort(v.begin(), v.end(), greater<pair<int, int>>());
            
            // 현재 전자기기 true하고, 가장 나중에 또는 사용하지 않을 전자기기를 false
            // 그리고 ans++
            power[cur] = true;
            power[v[0].second] = false;
            ans++;
        }
    }
    cout << ans;
}

후기

• 조건을 보고 그리디 알고리즘으로 이어지기까지는 쉬웠으나 구현이 까다로웠다.
• 지금까지 하던 것이 적절하지 않은 풀이라면 망설이지 말고 뒤엎자.
• 문제 많이 풀어보자