백준 1700 반례 (python)

#멀티탭 스케줄링 2022-02-16 22:18 start


N, K = map(int, input().split())

seq = list(map(int, input().split()))

plug = []
cnt = 0

for i in range(K):
    if seq[i] in plug:
        continue
    if len(plug) < N:
        plug.append(seq[i])
        continue

    idxs = []

    for j in range(N):
        if plug[j] in seq[i:]:
            idx = seq[i:].index(plug[j])
        else:
            idx = 101
        idxs.append(idx)

    del plug[idxs.index(max(idxs))]
    plug.append(seq[i])
    cnt += 1

print(cnt)

반례

---

2 15
3 1 2 1 2 1 2 1 2 3 3 3 3 3 3

접근

---

• 처음엔 다음 플러그 숫자중에서 제일 횟수가 작은 종류(숫자)를 빼내면 된다고 생각
• 하지만 반례와 마찬가지로 3이 더 많이 쓰이지만, 나중에 쓰여서 결국 최소 콘센트보다 더 많이 쓰게 됨
• 나중에 쓰일 인덱스를 빼주는게 정답