1700번 멀티탭 스케쥴링

문제

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

접근 방식

그리디 전략을 잘 세우는 것을 넘어, 개인적으로 고려할 게 많은 문제였다. 처음에는 그리디 전략은 멀티탭에 꽂혀있는 물건의 남은 횟수 중 제일 작은 것으로 풀었는데, 한참 헤매다보니 전략 자체가 틀렸다는 걸 알았다. (즉, 최적의 선택이 아님)

가장 나중에 나올/또는 아예 나오지 않는 물건의 플러그를 뽑아야 최적의 선택이다.

코드

def solution(orders, n, k):
    plug = []
    res = 0
    for i in range(k):
        if orders[i] in plug:
            continue
        if len(plug) < n:
            plug.append(orders[i])
            continue
        note = [k-i] * n #해당 물건이 orders 내에서 가장 빨리 등장하는 위치-현재 위치, plug와 대응
        for m in range(n):
            flag = False #가장 빨리 등장할 때  break하기 위해
            for j in range(i, k):
                if orders[j] == plug[m]:
                    note[m] = j-i
                    flag = True
                    break
            if flag: continue
        #가장 나중에 등장하는 물건의 플러그를 뽑기
        biggest = -float('inf')
        idx = 0
        for m in range(n):
            if biggest < note[m]:
                biggest = note[m]
                idx = m
        plug[idx] = orders[i]
        res += 1
    return res

n, k = map(int, input().split())
orders = list(map(int, input().split()))
print(solution(orders, n, k))