[코딩테스트 준비] 백준 골드 1문제(1700 멀티탭 스케줄링)

문제 핵심 요약

• 멀티탭 구멍 수: N
• 전기용품 사용 순서 길이: K
• 이미 꽂혀 있는 전기용품은 다시 꽂을 필요 없음
• 멀티탭이 꽉 찼는데 새로운 전기용품을 사용해야 하면 하나를 반드시 빼야 함
• 목표: 플러그를 빼는 횟수 최소화

 

핵심 아이디어 (그리디 전략)

멀티탭이 꽉 찬 상태에서 새로운 전기용품을 꽂아야 할 때:

앞으로 가장 늦게 다시 사용되거나, 아예 다시 사용되지 않는 전기용품을 뽑는다

이게 항상 최적이다.

왜냐하면?

• 곧 다시 쓸 전기용품을 뽑으면, 가까운 미래에 다시 꽂아야 해서 손해
• 반대로 다시 안 쓰거나 가장 나중에 쓰는 것을 뽑으면 가장 오래 유지 가능

→ OPT(Optimal Page Replacement)와 동일한 논리

 

알고리즘 흐름

1. 현재 멀티탭 상태를 vector 또는 set으로 관리
2. 전기용품 사용 순서를 처음부터 끝까지 순회
3. 각 전기용품에 대해:
   • 이미 꽂혀 있으면 continue
   • 빈 자리가 있으면 그냥 꽂기
   • 빈 자리가 없으면:
     • 현재 꽂힌 전기용품들 중
       • 다음 사용 시점이 가장 늦은 것 또는
       • 다시 사용되지 않는 것
     • 을 찾아 제거
     • 제거 횟수 +1

 

구현 포인트

• next use를 찾기 위해 현재 시점 이후를 선형 탐색
• K ≤ 100 이라서 O(NK²)도 충분히 통과
• 구현 난이도보다 그리디 판단이 핵심