1700 멀티탭 스케줄링 파이썬 풀이

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

1700번: 멀티탭 스케줄링

일단 문제에서 요구하는 대로 풀이를 작성한 후, 뭔가 함정이 있을거라고 생각하고 제출했는데 한번에 통과해서 놀랐다.

이 문제가 탐욕법, 그리디 기법이 어떤식으로 사용되었는지는 고찰이 필요해보인다.

 

문제의 요구사항

멀티탭에 슬롯이 N개 있고, 제한된 수량의 몇 가지 제품을 K번에 걸쳐서 순서대로 사용한다. 제품 종류는 최대 K개이며, 종류가 K보다 적을 경우 중복사용이 가능한듯하다. 이때, 슬롯에 자리가 있으면 그냥 끼워서 사용하고, 자리가 부족하다면 다른 제품의 코드를 뽑아서 새제품을 꼽는다. 코드를 뽑는 최솟값을 구하여라.

 

문제 해결 방법

2가지 기준으로 코드를 짜면된다.

우선, 멀티탭의 슬롯에 최대로 물건을 채운다

첫째로, 앞으로 사용할 예정이 없는 물건일 경우 순서 고려 없이 멀티탭에서 제거한다. 

둘째, 첫째 경우에 해당되지 않을 경우에는 멀티탭에 꼽혀있는 제품 중 가장 먼 미래에 사용예정인 제품을 제거한다. 

 

N, K = map(int, input().split())
products =list(map(int,input().split()))

multi=[]
count=0

for i in range(K):
    if len(multi)<=N and products[i] not in multi:  #멀티탭 Slot N에 최대로 물건 append
        multi.append(products[i])
    if len(multi)>N: #Slot 넘어서면, 1개 빼줘야한다.  2가지 기준이 있다.
        maxi=-1
        for j in range(N):
            A=products[i+1:K] #앞으로 사용할 물건 list A 생성
            if multi[j] not in A:    #기준1. 앞으로도 사용하지 않을 물건 있다면 제거하고 루프 종료
                multi.remove(multi[j])
                count+=1
                break
            else:
                maxi=max(maxi,A.index(multi[j])) #기준2. 멀티탭에 사용 예정이 있는 물건만 있는 경우, 가장 나중에 사용할 물건 찾기
        if len(multi)>N:
            multi.remove(A[maxi]) # 가장 나중에 쓸 물건 멀티탭에서 제거.
            count+=1

print(count)