1700번: 멀티탭 스케줄링
기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
N, K = map(int, input().split())
A = list(map(int, input().split()))
multitab = [A[0]]
change_count = 0
for i in range(1, K):
current_device = A[i]
try:
unplug_device_idx = 0
next_use_idx = A.index(multitab[unplug_device_idx], i, K)
except ValueError:
next_use_idx = 101
for j in range(1, len(multitab)):
try:
idx = A.index(multitab[j], i, K)
if next_use_idx <= idx:
next_use_idx = idx
unplug_device_idx = j
except ValueError:
next_use_idx = 101
unplug_device_idx = j
if current_device not in multitab:
if len(multitab) == N:
del multitab[unplug_device_idx]
change_count+=1
multitab.append(current_device)
print(change_count)
|
cs |
멀티탭에 우선 첫번째 순서의 디바이스를 꽂는다. 두번째 순서의 디바이스부터 순회하면서 멀티탭에서 교체할 디바이스를 찾는다.
교체할 디바이스를 찾는 기준은 아래와 같다.
현재 멀티탭에 꽂혀있는 디바이스 중 다음 사용 순서가 가장 나중인것을 찾아 해당 디바이스의 인덱스를 저장한다. 이 과정이 필요한 이유는 가장 나중에 사용될 디바이스를 가장먼저 교체해주기 위함이다.
[9-13 라인] 우선 초기화를 위해 멀티탭에 꽂혀있는 첫번째(0) 디바이스를 가장 나중에 사용할 디바이스로 지정하는데 이때 멀티탭에 꽂혀있는 첫번째 디바이스가 앞으로 사용할 계획이 없다면, 즉, A 리스트에 더이상 등장하지 않는다면 해당 디바이스는 교체대상 1순위이므로 다음 사용 순서를 가장 나중을 뜻하는 101로 지정하였다.
[15-23 라인] 현재 멀티탭에 꽂혀있는 두번째 디바이스부터 순회하면서 가장 나중에 사용할 디바이스의 인덱스를 찾는다. next_use_idx 는 거리의 max 를 저장하기 위한 변수이며 unplug_device_idx 는 거리가 가장 먼 디바이스의 멀티탭의 인덱스이다.
[25-30 라인] 멀티탭이 3구라고 가정할때 (즉, N 이 3이라면) 멀티탭에 3개의 디바이스가 다 꽂혀있지 않다면 굳이 교체할 필요가 없으므로 그냥 멀티탭에 꽂기만 하면되고,
멀티탭에 3개의 디바이스가 모두 꽂혀있다면 위에서 구한 교체할 인덱스로 멀티탭에서 삭제처리 한 후, 교체한 횟수를 + 1 해준다.
후기. 처음에는 가장 나중에 사용할 디바이스를 교체하지 않고 가장 작게 사용할 계획을 가진 기기 부터 교체하였다가 한동안 헤매다가 가장 나중에 사용할 디바이스를 먼저 교체하는 쪽으로 방향을 잡았다.
그러고나서도 한동안 헤맸는데, 그 이유는 처음부터 모든 멀티탭에 디바이스를 끼워놓고 시작하는거로 오해를 했다.
N=3, K=6 일 때
1 1 1 1 2 3 인 경우 답이 0이라는게 처음엔 이해가 가지 않았다.
이해가 가지 않은 이유는
1 1 1
1 1 1
1 1 2
1 1 3
으로 답이 3이 나와야 하는게 아닌가 하고 생각했던것이다.
하지만 이 경우 올바른 해석은
1 x x
1 x x
1 x x
1 x x
1 2 x
1 2 3
으로 단 한번의 교체도 없이 가능하다.
암튼 꽤 오래 헤맨 문제다. 이건 그리디 라고 해야하나..
알고리즘의 피지컬이 많이 요구되는 문제인듯..