백준 1700 - 멀티탭 스케쥴링 (Python)

문제

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

1700번: 멀티탭 스케줄링

풀이

n,k = map(int,input().split())
name = list(map(int,input().split()))
tap = [0] * n
i=0
answer = 0
while i<k:
    if name[i] in tap:
        i+=1
        continue

    for j in range(n):
        if tap[j] == 0:
            tap[j] = name[i]
            i+=1
            break
    else:
        nextPos = [k] * n
        for j in range(n):
            for l in range(i,k):
                if name[l] == tap[j]:
                    nextPos[j] = l
                    break
        
        maxPos = 0
        maxVal = nextPos[0]

        for j in range(n):
            if maxVal < nextPos[j]:
                maxPos = j
                maxVal = nextPos[j]
        
        tap[maxPos] = 0 
        answer += 1
print(answer)

그리디 알고리즘 문제이다.

개인적으로 그리디 알고리즘 문제를 풀 때 마다, 해결방법 구상이 상당히 까다롭다고 느낀다.

 

이번 문제의 경우 멀티탭을 뽑을 때, 멀티탭에 꽂혀있는 전기 용품 중 가장 나중에 다시 사용될 것을 뽑으면 되는 문제이다.

짧은 기간 안에 다시 사용될 용품을 뽑을 경우 결국 다시 해당 용품을 꽂아야 되기 때문에 가장 늦게 다시 사용될 물건부터 뽑아서 쓰는 것이다.

 

while문 내부의 조건은 다음과 같다.

1) 이미 꽂혀있는경우 -> 그냥 패스

2) 빈자리가 있는경우 -> 해당 자리에 꽂기

3) 빈자리가 없는경우 -> 가장 나중에 다시 사용될 제품의 코드를 뽑기, answer에 1 더하기

 

위 과정을 반복하여 모든 전자용품이 사용되면 뽑은 코드의 횟수(answer)를 출력해준다.