[백준] 1700 멀티탭 스케줄링

문제 링크

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

사용 알고리즘

• 그리디

풀이

한정된 수량의 플러그에 각 전기용품을 순서대로 사용해야 할 경우에서

플러그를 최소한으로 빼며 모든 전기용품을 사용하려면 몇 번 플러그를 빼야하는지 구하는 문제이다.

 

여기서 중요한 점은 각 전기용품을 순서대로 사용해야 하기 때문에 전기용품을 사용하는 순서에 따라 가중치를 주어야 한다는 점이다.

플러그를 빼야 할 경우(현재 멀티탭에 꽂혀있는 전기용품의 개수가 k 이상일 경우),

현재 멀티탭 안에 꽂혀있는 전기용품들의 가중치를 구한 뒤 가중치가 가장 낮은 전기용품을 빼면 된다.

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

n, k = map(int, input().split())
arr = [*map(int, input().split())]

now = set()


def get_remove(idx):
    res = []

    # 현재 꽂혀있는 전기용품들의 이후 가중치를 구한다.
    for e in now:
        t = 0
        for i in range(idx + 1, k):
            if arr[i] != e: continue
            # 비트 연산을 통해 순서에 따른 가중치를 구한다.
            t |= (1 << (k - i))
        res.append((t, e))
    
    # 가중치 순으로 정렬
    res.sort()

    # 가중치가 가장 낮은 전기용품을 반환한다.
    return res[0][1]


res = 0
for i in range(k):
    # 이미 꽂혀있는 경우 무시
    if arr[i] in now: continue
    # 아직 빈 플러그가 있는 경우 무시
    if len(now) < n:
        now.add(arr[i])
        continue
    
    # 가중치가 가장 낮은 전기용품을 빼고 새로운 전기용품을 꼽는다.
    res += 1
    now.remove(get_remove(i))
    now.add(arr[i])

print(res)