https://www.acmicpc.net/problem/1700
1700번: 멀티탭 스케줄링
기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전
www.acmicpc.net
다행히 이 문제는 아주 어려운 그리디 문제는 아니다. 그리디 문제가 어려우면 정말 어려울 때가 있다. 그리디 문제의 어려운 점은 증명이다. 가끔 어떠한 직관에 의해 풀이가 떠오르고, 그대로 구현했을 때 정답인 경우가 있다. 하지만 그 풀이의 증명이 쉽지 않다.
이 문제의 그 '직관'은 가장 마지막에 다시 사용할 기기를 가장 먼저 뺀다는 것이다. (물론 한번 사용한 기기를 다시 쓰는 일이 없다면 현재 꼽혀있는 플러그 중에 아무거나 뽑으면 된다.)
- 가장 먼저 다시 쓰는 기기의 플러그는 되도록 남겨둔다.
- 가장 자주 쓰는 기기의 플러그는 되도록 남겨둔다.
위의 생각들을 해보았다. 가장 '먼저'의 반대인 가장 '나중에' 다시 쓸 기기의 플러그를 남기는 건 당연히 말이 안 된다. 그 나중에 쓸 기기를 위해 다른 플러그들을 불필요하게 뽑아야 할 수 있기 때문이다. 가장 자주 쓰는 기기의 플러그를 남겨두는 것도 옳지 않다. 왜냐면 앞서 살펴본 첫 번째 케이스가 이미 포함된다. 가장 자주 쓰는 기기가 나중에 쓰일 경우, 그 사이에 다른 플러그들의 불필요한 움직임(?)이 생긴다.
콘센트 플러그가 5개라면, 한번에 한 개씩이므로
가장 먼저 다시 쓰일 기기를 1개 찾았다고 멈추면 안 된다. n-1개, 즉 4개를 찾아내야 한다.
4개를 찾고 나서 남는 기기를 뽑아야 한다.
문제의 N 상한이 100이므로 N 제곱을 해도 1만 번뿐이다.
- 플러그에 남은 자리가 있으면 그냥 꼽아주고 패스
- 자리 없으면 N-1개의 가장 먼저 다시 쓰일 기기들을 찾는다. 그리고 쓰이지 않는 기기의 플러그를 뽑는다.
- 스케쥴의 마지막까지 다 확인해도 다시 쓰일 기기가 N-1개까지 되지 않는다면 그냥 플러그에서 뽑을 수 있는 것들 중에 아무거나 뽑는다.
<알고리즘>
그리디
<코드>
import sys
import copy
si = sys.stdin.readline
n, k = [int(e) for e in si().split()]
arr, hold, cnt = [int(e) for e in si().split()], set(), 0
for i, e in enumerate(arr):
if len(hold) < n or e in hold:
hold.add(e)
continue
left_over, stay, take_out = n, set(), 0
for j in range(i, k):
if arr[j] in hold:
if arr[j] not in stay:
stay.add(arr[j])
left_over -= 1
if left_over == 1:
take_out = list(hold-stay)[0]
break
if not take_out:take_out = list(hold)[0]
hold.remove(take_out)
cnt += 1
hold.add(e)
print(cnt)
