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

INF = 1e6
import sys
input = sys.stdin.readline

def BOJ1700() :
  N, K = map(int, input().split())
  arr = list(map(int, input().split()))
  count = 0

  plugins = []
  
  for i in range(K) :
    if arr[i] in plugins:
      continue

    if len(plugins) < N :
      plugins.append(arr[i])
      continue
    
    after_use_index = []
    remains = arr[i:]
    
    for j in range(N) :
      if plugins[j] not in remains :
        after_use_index.append(101)
        continue

      after_use_index.append(remains.index(plugins[j]))

    plug_out_index = after_use_index.index(max(after_use_index))
    del plugins[plug_out_index]
    plugins.append(arr[i])
    count += 1

  print(count)

BOJ1700()

 

풀이 접근 방법 :

1. 멀티탭에 꽂을 수 있으면 꽂는다.

2. 멀티탭에 꽂혀 있다면 넘어간다.

3. 멀티탭은 이미 full 이면 아직 사용이 남아있는 list에서 제일 나중에 쓰는 인덱스를 가져온다. 
그리고 해당 index의 값에 해당하는 번호를 현재 멀티탭에서 빼낸다. 

그리고 count + 1

 

1~3을 반복한다

3번에서 가장 나중에 쓰는 도구를 현재 멀티탭에서 빼내는 것이 핵심이다 -> 그리디

제일 처음에 시도는 나중에 쓰는 도구들중 count를 하여 가장 적게 쓰는 애를 뽑았다. -> 오답

가장 적게 쓰는 애를 뽑는것은 최소한으로 멀티탭을 뽑는것을 보장해주지 못한다.

(예시) 1 2 3 4 3 4 2 2 

따라서 현재에 가장 최선의 선택인 가장 나중에 쓰이는 도구를 현재의 멀티탭에서 뽑아주었다.

 

 

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

1700번: 멀티탭 스케줄링