[python] 백준 - 1700 (멀티탭 스케줄링)

2025.12.26ko 0 시리즈 · 알고리즘 #알고리즘

골드1 문제이며, 제한 시간은 2초이다.

문제

해결 과정

이 문제는 처음에 접근했던 방식과 해결했던 과정이 달라서 시간을 정말 많이 썼다.

우선 처음에 생각했던 방식은 전기용품을 입력받고, 이 용품들의 빈도를 저장해서 처음에 꽂아 놓는 전기용품을 빈도순으로 꽂으려 했다. 그리고 전기용품을 뺄 때, 현재 꽂혀있는 전기용품들 중 빈도가 낮은 전기용품을 빼는 방식을 생각했다. 하지만 이 방식은 장기적으로 최적의 해를 구해줄 수가 없었다.

이 문제를 해결하는데에 있어서 중요한 아이디어는 아래와 같다.

현재 꽂혀있는 전기용품 중 가장 나중에 다시 꽂아야 하는 전기용품을 뽑는 것

이렇게 동작한다면 전기용품을 최소로 뽑는 경우를 구할 수 있을 것이다. 저 아이디어를 생각하기가 정말 어려운 것 같다.

풀이

n, k = map(int, input().split())
arr = list(map(int, input().split()))
now = []
answer = 0

for i in range(k):
  if arr[i] in now:
    continue
    
  if len(now) < n:
    now.append(arr[i])
    continue

  #현재 꽂혀있는 전기용품 중에서 다음에 언제 등장하는지 기록
  #등장하지 않는다면 K로 설정해서 제일 나중에 등장한다고 생각함
  next_use = [k] * len(now)
  for j in range(len(now)):
    for t in range(i + 1, k):
      if now[j] == arr[t]:
        next_use[j] = t
        break
  #현재 꽂혀있는 전기용품 중 등장을 제일 늦게하는 전기용품을 뽑고
  #현재 탐색중인 전기용품을 꽂는다.
  idx = next_use.index(max(next_use))
  now.pop(idx)
  now.append(arr[i])
  answer += 1

print(answer)

어려운 문제였던만큼 가물가물해질 때, 다시 풀어봐야겠다.

아직 댓글이 없습니다.

문제

해결 과정

풀이

댓글

댓글 쓰기