(Python) - BOJ(1700번) : 멀티탭 스케줄링

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

---

• 해설 : 

준규의 가전제품 사용 순서와, 멀티탬의 구멍 개수가 주어질 때, 모든 가전제품을 사용하기 위해 플러그를 최소한으로 빼는 횟수를  구하는 문제이다.

 

 

 

---

• 풀이 :

그리디하게 해결하였다. 현재 플러그가 꽉 차있을 때부터 replacement가 발생하는데  이 때 남은 프로세스들 중 빈도가 가장 낮은 프로세스를 대체하면 된다.

 

이 문제에서 사용된 replacement 방법은 프로세스의 replacement 방법둘 즁, 가장 비효율적이라고 알려진 남은 프로세스 실행 빈도를 판단하여 replacement하는 것이다. 

이 문제에서 이와 같은 방법이 가능한 것은 프로세스의 길이가 고정적이라는 점 때문인 것 같다.

 

 

 

---

• 소스코드 : 

 

 

n, k = map(int, input().split())
s = list(map(int, input().split()))
m = [0 for i in range(n)]
cnt = 0
for i in range(k):
    isTrue = False
    for j in range(n):
        if m[j] == s[i] or m[j] == 0:
            isTrue = True
            m[j] = s[i]
            break
    if isTrue:
        continue
    else:
        a = 0
        for j in range(n):
            try:
                if a < s[i + 1:].index(m[j]):
                    a = s[i + 1:].index(m[j])
                    b = j
            except:
                a = -1
                b = j
                break
        m[b] = s[i]
        cnt += 1
print(cnt)