[백준] 1700. 멀티탭 스케줄링 - 파이썬
https://www.acmicpc.net/problem/1700
1700번: 멀티탭 스케줄링
기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전
www.acmicpc.net
풀이
플러그를 새로 꽂을 때마다 경우의 수가 나눠지는데
- 플러그 자리가 남아 있을 때
- 꽂혀 있는 기기를 그대로 사용
- 플러그 하나를 빼야 함.
1, 2번은 그냥 처리하면 되고,
3번을 처리하는 방법이 문제다.
Greedy하게 처리하자면, 앞으로 쓸 일이 없거나, 가장 나중에 사용할 기기를 빼는 것이 최선이므로, 그렇게 처리함.
from collections import deque
import sys
read = sys.stdin.readline
def index(x):
if x not in elecs:
return -1
else:
return elecs.index(x)
N, k = map(int, read().strip("\n").split())
elecs = list(map(int, read().strip("\n").split()))
tap = deque([])
eleclist = elecs[:]
elecs = deque(elecs)
answer = 0
for elec in eleclist:
if elec in tap:
elecs.popleft()
continue
elif len(tap) < N:
tap.append(elecs.popleft())
else:
lastindex = 0
for n in tap:
j = index(n)
if j == -1:
tap.remove(n)
lastindex = -1
break
else:
if j > lastindex:
lastindex = j
if lastindex != -1:
tap.remove(elecs[lastindex])
tap.append(elecs.popleft())
answer += 1
print(answer)