Boj 1700 c++멀티탭 스케줄링

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

 

 

문제

N개의 플러그가 있는 멀티탭이 있다. 전기용품을 사용하는 순서가 주어질 때, 플러그를 최대한 빼지 않고 모든 전기용품을 사용하였을 때, 플러그 교체 횟수를 구해야 한다.

 

예를 들어 플러그 수가 3개인 멀티탭에

 

키보드 -  드라이기 - 핸드폰 충전기 - 카메라 충전기 - 키보드 - 드라이기

 

순서로 사용해야 한다고 할때, 카메라 충전기를 핸드폰 충전기와 교체하면 플러그를 1번만 교체하고도 모든 전기용품을 사용할 수 있다.

 

 

입력 조건 

멀티탭 플러그의 수 N과 전기용품 사용 패턴의 길이 K가 주어진다.

두번째 줄부터 길이가 K인 패턴이 주어진다.

 

풀이

플러그의 개수를 페이지의 크기라고 생각하면, 회의실 배정 문제와 비슷한 결의 스케줄링 문제로 변한다.

이 문제에서는 페이지 교체 횟수를 최소화하여야 한다. 그렇다면 페이지를 교체할 가능성이 가장 적도록 적절히 전기용품을 교체하여야 한다.

 

회의실 배정 문제에서는 가장 빨리 끝나는 회의를 진행하여, 남은 시간 동안 할 수 있는 회의의 개수가 최대가 되도록 하였다.

그렇다면 이 문제에서는 전기용품들의 정보를 바탕으로 앞으로 가장 오랫동안 사용하지 않을 전기용품을 교체하여  앞으로 추가로 교체될 가능성을 줄이면 되는 것인가.

 

증명

 

현재 플러그에는 전기용품 A, B, C가 있다고 해보자.

A

B

C

 

프로세스가 다음과 같다고 해보자.

'...' 구간에서는 A, B, C가 사용되지 않는다고 가정한다.

 

A - B - C - D ....................... - A - B

 

4번째 전기용품 D를 사용하기 위해서는 A, B, C 중에서 하나를 교체해야 한다.

이때, C를 교체하는 경우, 플러그는

A

B

D

 

와 같은 상태가 된다. 이때, 다시 C를 사용하기 위해서 페이지를 교체하지 않아도 된다.

D를 기준으로 생각했을 때 이후에 C가 등장하지 않기 때문이다.

 

하지만 A 또는 B를 교체한다면 또 다시 A, B를 사용하기 위해 페이지를 교체해야 하는 경우가 발생한다.

 

아예 등장하지 않는 경우를 제외하더라도 가장 오랫동안 사용되지 않을 프로세스를 교체하는 것이 유리하다.

현재 시점을 기준으로 생각하였을 때 교체할 프로세스가 '사용되지 않을 기간'은 길 수록 좋다.

더 일찍 사용될 프로세스들을 남겨놓는 것이 교체 횟수를 최소화 할 수 있기 때문이다.

 

즉, 가장 필요도가 낮은 것을 교체하는 것이다.

 

페이지에 존재하지 않는 새로운 프로세스가 등장하였을 때 

페이지 폴트는 불가피하게 발생하게 된다. 우리는 여기서 이후의 페이지 폴트를 최소화하는 방향으로 나아가야 한다.

 

가장 멀리 있는 것을 교체하는 것 외의 다른 방법들을 고려하였을 때, 해당 방법을 사용하였을 때 손해를 보지 않는다.

즉, 해당 방법이 최적인 것이다.

 

쓰다보니 내가 설명하는데에도 불구하고 잘 납득이 되지 않는다.

 

직관적으로 설명하자면 어쩔 수 없이 페이지를 교체해야 하는 상황에서는 기왕이면 가장 쓸모없는 것을 교체한다고 생각하면 된다.

일찍 등장하면 이후에도 필요할 가능성이 높지만, 늦게 등장할 수록 다시 쓰일 가능성이 낮은 까닭이다.

 

 

 

구현

 

증명까지 해놓고 구현에서 애먹었다.

전기용품의 사용 프로세스를 처리하는 방법은 다음과 같은 순서를 따라야 한다.

 

1. 해당 전기용품이 플러그에 이미 존재할 때 continue

2. 플러그가 아직 가득 차지 않았다면 플러그에 추가하기

3. 이후 전기용품 사용 계획을 토대로 가장 오랫동안 사용되지 않을 전기용품 교체

 

교체할 전기용품을 고를 때에는 현재 시점을 기준으로 하여 해당 전기용품이 처음으로 다시 쓰이기 까지의 기간을 고려한다.

아예 등장하지 않는 경우에는 해당 전기용품을 교체하는 것이 최적이므로 반복문을 탈출해야 한다.

 

 

풀이코드

 

#include <iostream>
using namespace std;

int arr[101], page[101], N, K;  // N : 플러그 수 K : 사용할 제품 패턴 길이

bool in_page(int n) {
    for(int i = 0; i < N; i++) {
        if(page[i] == n)
            return true;
    }
    return false;
}

int main() {

    cin >> N >> K;

    for(int i = 0; i < K; i++) {
        cin >> arr[i];
    }

    int pg = 0, ans = 0;

    for(int i = 0; i < K; i++) {
        if(in_page(arr[i])) {
            continue;
        } else if(pg < N) {
            page[pg++] = arr[i];  // 페이지가 비어있다면 채워준다
        } else {
            int most_not_used = i;
            int max_idx;
            for(int j = 0; j < N; j++) {// 각각의 페이지 전기용품에 대해서
                bool found = false;
                for(int l = i; l < K; l++) { // 현재 상태를 기준으로 생각해야 한다
                    if(page[j] == arr[l]) {
                        found = true;
                        if(most_not_used < l) {
                            most_not_used = l;
                            max_idx = j;
                        }
                        break;
                    }
                }
                if(!found) {
                    max_idx = j;
                    break;
                }
            }
            page[max_idx] = arr[i];  // 가장 오랫동안 사용되지 않을 페이지 교체
            ans++;
        }
    }
    cout << ans;
}