1700. 멀티탭 스케줄링

최근 팀플땜에 바빠서.. 오랜만에 문제를 풀어 보았다.

1700번: 멀티탭 스케줄링

---

구멍이 $N$개인 멀티탭이 있고, $K$종류의 전자제품이 있다. 전자제품을 주어진 순서대로 총 $K$번 사용하려 할 때, 멀티탭에 꽂혀 있던 플러그를 최소한 몇 번 뽑아야 하는지 계산해야 한다.

 

문제를 읽자마자 그리디라는 감이 왔다. 

 

1. 멀티탭에 빈 플러그가 있다면 그냥 꽂으면 된다.

2. 사용하려는 전자제품이 이미 꽂혀 있으면 그냥 넘어가면 된다.

3. 멀티탭에 새로 꽂아야 하는데 빈 플러그가 없는 경우, 적당한 플러그를 빼야 한다. 이 경우에 현재 꽂혀 있는 전자제품 중 처음으로 사용되는 시점이 가장 늦은 플러그(이하 $p$)를 빼는 것이 항상 최선이다.

 

어째서 그러한가? $p$가 아닌 다른 전자제품을 뽑았다고 가정하면, 나중에 $p$를 사용하기 위해 $p$를 안 뽑았을 때보다 적어도 한 번 플러그를 더 뽑아야 한다. 따라서 $p$를 뽑는 것이 항상 최선이다.

 

뭔가 숨겨진 함정이 있을 것 같지만 그런 거 없다. 사소한 구현 실수만 주의하자.

---