[그리디 알고리즘]1700-멀티탭 스케줄링

백준 멀티탭 스케줄링이다.

 

먼저 멀티탭 스케줄링을 가장 간단한 언어로 요약하면,

n구의 멀티탭에 여러가지 전자제품을 사용하려는데(k개의 전자제품 사용 스케줄), 빼는 횟수를 최소화 하고 싶다는 것이다.

 

직관적으로 다음 아이디어가 떠오른다.

"그러면 그냥 다음에 나올 빈도수가 적은 것 먼저 뽑으면 되는거 아니야?"

그렇게 코딩을 시행해봤고, 광탈했다.

반례는 어렵지 않게 찾을 수 있었다.

 

"가장 늦게 나오는 플러그, 또는 절대 안나올 플러그를 먼저 뽑으면?"

이렇게 아이디어를 잡으면 다음 코드가 나온다.

import sys
input = sys.stdin.readline
n, k = map(int, input().rstrip().split())
con = list(map(int, input().rstrip().split()))
state = [0 for i in range(n)]
cont = 0
for i in range(k):
    if con[i] not in state:
        if 0 in state:
            for j in range(n):
                if state[j] == 0:
                    state[j] = con[i]
                    break
        else:
            maxi = -1
            maxx = 0
            for j in range(n):
                pan = 0
                for x in range(i, k):
                    if state[j] == con[x]:
                        if maxi < x:
                            maxi = x
                            maxx = j
                        pan = 1
                        break
                if pan == 0:
                    maxi = 10000
                    maxx = j
            state[maxx] = con[i]
            cont += 1
print(cont)

 

그리디는 한 번 유형 분석이 필요한 것 같다. 다음 글에서 유형 분석을 하도록 하겠다.