January 15, 2023

1700번: 멀티탭 스케줄링

문제 요약

• 구멍의 수가 N개이고, 전기 용품의 사용 순서가 주어질 때 멀티탭의 플러그를 빼는 최소 횟수 출력
• 1 ≤ N ≤ 100, 1 ≤ K ≤ 100

풀이

N, K = map(int, input().split())
order_list = list(map(int, input().split()))
tab_list = []

cnt = 0

for i in range(len(order_list)):
    order = order_list[i]
    if (order in tab_list):
        continue
    elif (len(tab_list) < N):
        tab_list.append(order)
    else:
        cnt += 1
        remain_dis_list = []
        remain_order_list = order_list[i + 1::]
        for tab in tab_list:
            duplicate_dis = 0
            for remain_order in remain_order_list:
                if (remain_order != tab):
                    duplicate_dis += 1
                else:
                    break
            remain_dis_list.append(duplicate_dis)
        min_idx = remain_dis_list.index(max(remain_dis_list))
        del tab_list[min_idx]
        tab_list.append(order)

print(cnt)

• 각 플러그에 대해서
  • 이미 꽂혀있다면 패스
  • 멀티탭에 플러그가 남아있다면 꽂음
  • 멀티탭에 플러그가 남아있지 않다면, 가장 먼 시점에 다시 사용하는 플러그를 뽑음