이번 문제는 백준 골드 1 난이도의 대표적인 그리디 문제인 멀티탭 스케줄링입니다. 처음 보면 구현처럼 보일 수 있지만, 핵심은 지금 어떤 플러그를 뽑아야 이후에 가장 유리한가를 판단하는 데 있습니다. 이 글에서는 문제 아이디어, 왜 그리디가 되는지, 시각화, 코드 해설, 그리고 실수하기 쉬운 포인트까지 한 번에 정리해보겠습니다.
핵심 요약
- 이미 꽂혀 있는 기기라면 그냥 사용하면 됩니다.
- 빈 구멍이 있다면 새 기기를 그냥 꽂으면 됩니다.
- 꽂을 자리가 없으면 앞으로 가장 늦게 다시 쓰이거나, 다시는 쓰이지 않는 기기를 뽑아야 합니다.
- 즉, 현재 순간에서 미래 사용 순서를 보고 가장 손해가 적은 선택을 하는 전형적인 그리디입니다.
- 정답은 플러그를 뽑은 횟수의 최솟값입니다.
1. 문제 설명
멀티탭 구멍의 개수 N 과 전기용품 사용 순서 K 개가 주어집니다. 각 순서마다 필요한 기기를 사용해야 하고, 멀티탭에 자리가 없으면 어떤 기기의 플러그를 뽑아야 합니다. 이때 플러그를 뽑는 횟수를 최소화하는 것이 목표입니다. [문제 출처](https://www.acmicpc.net/problem/1700)
중요한 점은 지금 당장 가장 덜 중요한 기기를 뽑는 것이 아니라, 앞으로 가장 나중에 다시 사용할 기기를 뽑아야 한다는 것입니다. 이 한 가지 기준만 정확히 잡으면 문제 풀이가 깔끔해집니다.
2. 왜 그리디로 풀 수 있을까?
멀티탭이 가득 찼을 때 어떤 플러그를 뽑을지 선택해야 합니다. 이때 최선의 선택은 다음 두 경우 중 하나입니다.
- 앞으로 다시 사용되지 않는 기기가 있다면 그 기기를 바로 뽑는다.
- 모든 기기가 앞으로 다시 사용된다면, 그중에서 가장 나중에 다시 쓰이는 기기를 뽑는다.
이유는 간단합니다. 어차피 더 늦게 쓰이는 기기를 빼야 앞으로 당장 필요한 기기를 다시 꽂는 불필요한 상황을 줄일 수 있기 때문입니다. 즉 현재 순간의 최선의 선택이 전체 최적해로 이어지는 구조라서 그리디가 성립합니다.
멀티탭이 꽉 찼다면
다시 안 쓰이는 기기 > 가장 늦게 다시 쓰이는 기기 순으로 뽑는다
3. 시각화로 이해하기
예를 들어 멀티탭 구멍이 3개이고, 사용 순서가 [1, 2, 3, 4, 1, 2] 라고 해보겠습니다.
단계별 멀티탭 상태
1 사용 → [1]
2 사용 → [1, 2]
3 사용 → [1, 2, 3]
4 사용 필요, 자리가 없음 → [1, 2, 3] 중 누구를 뽑을까?
앞으로의 사용 순서: [1, 2]
1은 다시 사용됨, 2도 다시 사용됨, 3은 다시 사용되지 않음 → 3을 뽑는다
최종 교체: [1, 2, 4], 플러그 제거 횟수 +1
핵심 포인트
자리가 없을 때는 단순히 아무거나 빼는 것이 아니라, 앞으로 가장 필요 없는 기기를 제거해야 합니다. 다시 안 쓰이는 기기가 있으면 그게 최우선이고, 모두 다시 쓰인다면 가장 나중에 다시 등장하는 기기를 빼면 됩니다.
4. 코드
아래 코드는 네가 작성한 풀이 그대로이며, 미래 사용 순서를 직접 확인하면서 어떤 기기를 뽑을지 결정하는 방식입니다.
Python
# 그리디 - 멀티탭 스케줄링 (백준 골드1)
# 문제 링크: https://www.acmicpc.net/problem/1700
n, k = map(int, input().split())
multi = list(map(int, input().split()))
cnt = 0
result = []
for i in range(k):
if multi[i] in result:
continue
if len(result) < n:
result.append(multi[i])
continue
idx = -1
farthest = -1
for j in range(n):
if result[j] not in multi[i+1:]:
idx = j
break
else:
next_use = multi[i+1:].index(result[j])
if next_use > farthest:
farthest = next_use
idx = j
result[idx] = multi[i]
cnt += 1
print(cnt)
5. 코드 한 줄 한 줄 설명
이 코드는 현재 멀티탭 상태를 result 에 저장하고, 자리가 없을 때만 누굴 뽑을지 결정하는 구조입니다.
| 라인 |
코드 |
설명 |
| 1 |
n, k = map(int, input().split()) |
멀티탭 구멍 개수와 전체 사용 횟수를 입력받습니다. |
| 2 |
multi = list(map(int, input().split())) |
기기 사용 순서를 리스트로 저장합니다. |
| 3 |
cnt = 0 |
플러그를 뽑은 횟수를 저장하는 변수입니다. |
| 4 |
result = [] |
현재 멀티탭에 꽂혀 있는 기기들을 저장합니다. |
| 5 |
for i in range(k): |
사용 순서를 앞에서부터 하나씩 확인합니다. |
| 6 |
if multi[i] in result: |
지금 필요한 기기가 이미 꽂혀 있다면 아무 작업도 필요 없습니다. |
| 7 |
continue |
다음 사용 순서로 넘어갑니다. |
| 8 |
if len(result) < n: |
멀티탭에 빈자리가 있는지 확인합니다. |
| 9 |
result.append(multi[i]) |
빈자리가 있으면 그냥 현재 기기를 꽂습니다. |
| 10 |
continue |
플러그를 뽑을 필요가 없으니 다음 순서로 갑니다. |
| 11 |
idx = -1 |
어느 위치의 기기를 뽑을지 저장할 인덱스를 초기화합니다. |
| 12 |
farthest = -1 |
가장 늦게 다시 쓰이는 시점을 기록하는 변수입니다. |
| 13 |
for j in range(n): |
현재 꽂혀 있는 모든 기기를 하나씩 확인합니다. |
| 14 |
if result[j] not in multi[i+1:]: |
현재 기기가 앞으로 다시 사용되지 않는다면, 그 기기를 뽑는 것이 최선입니다. |
| 15 |
idx = j |
뽑을 대상의 인덱스를 기록합니다. |
| 16 |
break |
다시 안 쓰이는 기기를 찾았으니 더 볼 필요 없이 바로 결정합니다. |
| 17 |
else: |
앞으로 다시 사용된다면, 그 사용 시점을 비교해야 합니다. |
| 18 |
next_use = multi[i+1:].index(result[j]) |
현재 시점 이후에서 해당 기기가 몇 번째 뒤에 다시 등장하는지 구합니다. |
| 19 |
if next_use > farthest: |
가장 늦게 다시 등장하는 기기인지 확인합니다. |
| 20 |
farthest = next_use |
가장 늦은 사용 시점을 갱신합니다. |
| 21 |
idx = j |
현재 기준으로 가장 늦게 쓰이는 기기의 위치를 기록합니다. |
| 22 |
result[idx] = multi[i] |
선택한 기기를 뽑고, 현재 필요한 기기를 그 자리에 꽂습니다. |
| 23 |
cnt += 1 |
플러그를 한 번 뽑았으므로 횟수를 증가시킵니다. |
| 24 |
print(cnt) |
최종적으로 최소 플러그 제거 횟수를 출력합니다. |
6. 예시로 다시 따라가기
위 예시 N=3, 순서=[1,2,3,4,1,2] 에서 실제 판단 과정을 표로 보면 더 명확합니다.
| 순서 |
현재 기기 |
멀티탭 상태 |
판단 |
제거 횟수 |
| 1 |
1 |
[1] |
빈자리 있으므로 꽂음 |
0 |
| 2 |
2 |
[1, 2] |
빈자리 있으므로 꽂음 |
0 |
| 3 |
3 |
[1, 2, 3] |
빈자리 있으므로 꽂음 |
0 |
| 4 |
4 |
[1, 2, 3] |
3은 앞으로 안 쓰이므로 3 제거 |
1 |
| 5 |
1 |
[1, 2, 4] |
이미 꽂혀 있음 |
1 |
| 6 |
2 |
[1, 2, 4] |
이미 꽂혀 있음 |
1 |
7. 이 풀이에서 중요한 구현 포인트
- result 는 현재 멀티탭 상태입니다.
- multi[i+1:] 는 현재 시점 이후의 미래 사용 순서입니다.
- not in 으로 다시 사용되지 않는 기기를 먼저 찾습니다.
- index() 로 가장 늦게 다시 등장하는 기기를 찾습니다.
- 다시 안 쓰이는 기기를 찾으면 바로 break 하는 것이 핵심입니다. 그보다 더 좋은 제거 대상은 없기 때문입니다.
8. 시간 복잡도
바깥 반복이 K번 돌고, 멀티탭 안의 기기 N개를 확인하면서 미래 배열을 탐색하기 때문에 구현상 여러 번의 리스트 탐색이 들어갑니다. 하지만 이 문제의 제한은 N, K 모두 100 이하 이므로 지금과 같은 방식으로도 충분히 통과할 수 있습니다. [문제 출처](https://www.acmicpc.net/problem/1700)
- 시간 복잡도: 최악의 경우 O(K × N × K) 정도로 볼 수 있습니다.
- 공간 복잡도: O(N)
9. 마무리
멀티탭 스케줄링은 그리디 문제에서 굉장히 유명한 유형입니다. 포인트는 지금 가장 덜 중요한 것이 아니라, 앞으로 가장 늦게 필요하거나 아예 필요 없는 것을 뽑는다는 점입니다. 이 기준만 잡히면 구현 자체는 생각보다 어렵지 않습니다.
멀티탭이 꽉 찼다면
다시 안 쓰이는 기기 또는 가장 늦게 다시 쓰이는 기기를 뽑는다
한 줄 결론
백준 1700은 미래 사용 순서를 기준으로 가장 손해가 적은 플러그를 제거하는 그리디 문제이고, 다시 안 쓰이거나 가장 늦게 다시 쓰이는 기기를 뽑는 것이 최적해입니다.