BOJ-1700 멀티탭 스케줄링

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

문제 소개

멀티탭의 콘센트 개수와 전기용품의 사용 순서가 주어졌을 때, 플러그를 빼는 횟수를 최소화하려고 한다.

문제 풀이

전기용품의 사용 순서는 리스트 arr에 저장하였다. arr의 첫 원소부터 해당 전기용품을 사용하기 위한 동작을 수행한다.

가장 먼저 해당 전기용품이 이미 멀티탭에 연결되어있는지를 확인한다. 이미 연결되어있다면 그대로 사용하면 되므로 연결되어있지 않은 경우만 고려한다.

연결이 필요한 경우에는 멀티탭에 몇 개의 전기용품이 연결되어있는지에 따라 동작이 달라진다.

1. 멀티탭의 모든 콘센트에 전기용품이 연결되어있는 경우

2. 빈 콘센트가 있는 경우

2번의 경우에는 빈 콘센트에 그대로 전기용품을 연결하면 되지만, 1번의 경우에는 이미 연결된 전기용품 중 뽑을 전기용품을 골라야 한다.

전기용품을 뽑는 우선순위는 아래와 같다.

1. 다시 사용될 일이 없는 전기용품이 연결되어 있다면 그것을 뽑는다.

2. 가장 오랫동안 다시 사용하지 않을 전기용품을 뽑는다.

즉, 현재로부터 다시 사용되기까지 가장 긴 시간을 요구하는 전기용품을 뽑으면 뽑는 횟수를 최소화할 수 있다.

전기용품을 뽑을 때마다 cnt를 누적시키고, arr 전체에 대해 동작이 끝나면 cnt를 출력한다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()

n, k = map(int, input().split())
arr = list(map(int, input().split()))

connecting = []

cnt = 0
for i in range(k):
    # arr[i]가 연결되어있지 않은 경우
    if arr[i] not in connecting:
        # 이미 n개가 연결된 경우
        if len(connecting) == n:
            # 마지막 전기용품인 경우
            if i == k - 1:
                # 아무 전기용품이나 뽑는다
                cnt += 1
                break
            else:
                # 다시 쓰이지 않는 전기용품이 꽂혀 있다면 뽑는다
                for j in connecting:
                    if j not in arr[i + 1:]:
                        connecting.remove(j)
                        break
                # 꽂혀있는 모든 전기용품이 다시 쓰이는 경우
                else:
                    # 가장 오랫동안 다시 사용하지 않을 전기용품을 뽑는다
                    t = [arr[i + 1:].index(j) for j in connecting]
                    connecting.pop(t.index(max(t)))
                cnt += 1
                connecting.append(arr[i])
        # 빈 콘센트가 있는 경우
        else:
            connecting.append(arr[i])
print(cnt)