[백준/파이썬] 1700번 멀티탭 스케줄링

 

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

1700번: 멀티탭 스케줄링

 

---

문제 & 테스트 케이스

---

문제 해석

준규는 N개를 꼽을 수 있는 멀티탭에 전기용품을 꽃아 사용한다.

K번 전기용품을 순서대로 사용할 때 전기용품의 플러그를 최소로 뽑는 횟수를 구하는 문제이다.

---

코드

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


# 몇 번 이후에 도착하는지 체크하는 배열
visit = [[float('inf')] * 101 for _ in range(101)]

# i번 위치에 존재하는 전기용품의 다음 index를 구하기
for i in range(1, k + 1):
    prev = -1
    for idx in range(1, len(arr)):
        now = arr[idx]
        if i == now:
            if prev == -1:
                prev = idx
            else:
                visit[i][prev] = idx
                prev = idx

def inn(idx, now):
    global concent_count
    global ans

    # 이미 꼽혀있다면 idx 갱신
    if concent[now]:
        concent[now] = idx
        return
    # 꼽힐 공간이 남아있다면 꼽고 idx 갱신
    elif concent_count < concent_max:
        concent[now] = idx
        concent_count += 1
        return

    # 뽑아야 하는 경우
    else:
        length = 0
        found = 0
        # 꽂혀있는 전기용품을 찾아 다음 index가 가장 뒤에 있는 전기용품을 뽑기
        for i in range(1, 101):
            if concent[i]:
                found += 1
                if visit[i][concent[i]] > length:
                    length = visit[i][concent[i]]
                    getout = i
                if found == concent_max: break
        # 뽑은건 idx 0 으로 갱신, 꼽은것 idx 갱신
        concent[getout] = 0
        concent[now] = idx
        ans += 1
        return

ans = 0
concent = [0] * 101
concent_count = 0
concent_max = n

for i in range(1, len(arr)):
    now = arr[i]
    inn(i, now)

print(ans)

---

문제 풀이

이 문제를 보면서 바로 컴퓨터 운영체제 내용에서 페이지 교체 알고리즘이 떠올랐다.

페이지 교체 알고리즘 중에서 가장 최적화된 알고리즘은 앞으로 가장 오래 사용되지 않을 프로세스를 제거하는 것이다.

하지만 현실적으로 어떤 프로세스가 올지 미래를 예측할 수 없으므로 이 알고리즘은 성능 계산의 기준으로 사용된다.

 

하지만 이 문제에서 우리는 순서를 알고 있기 때문에 가장 오래 사용되지 않을 전기용품을 알고 있다.

따라서 콘센트의 수가 모두 찼을 때, 가장 나중에 사용될 전기용품을 뽑으면 된다.

 

# i번 위치에 존재하는 전기용품의 다음 index를 구하기
for i in range(1, k + 1):
    prev = -1
    for idx in range(1, len(arr)):
        now = arr[idx]
        if i == now:
            if prev == -1:
                prev = idx
            else:
                visit[i][prev] = idx
                prev = idx

먼저 전기용품이 내가 사용되고, 다음에 사용될 인덱스를 구해주었다.

전기용품 i에 대해 먼저 이전 값이 처음에는 없으므로 -1로 지정했다.

첫 발견에는 현재 인덱스를 prev에 저장한다.

나중에 발견될 경우에는 visit[전기용품][이전 인덱스] 값에 현재 인덱스 값을 넣어준다.

즉, i번째 전기용품이 첫번째 발견되었던 위치에 두번째 발견된 위치 값을 넣어준 것이다.

이를 반복하면 다음 위치의 index값이 저장되게된다.

또한 애초에 visit 리스트를 inf 로 초기화 시켜 마지막으로 존재하는 전기용품에는 inf 값이 담기게 된다.

2	3	2	3	1	2	7
index(2)	index(3)	index(5)	index(inf)	index(inf)	index(inf)	index(inf)

주어진 예제에서 다음과 같은 값을 가지게 된다.

 

def inn(idx, now):
    global concent_count
    global ans

    # 이미 꼽혀있다면 idx 갱신
    if concent[now]:
        concent[now] = idx
        return
    # 꼽힐 공간이 남아있다면 꼽고 idx 갱신
    elif concent_count < concent_max:
        concent[now] = idx
        concent_count += 1
        return

    # 뽑아야 하는 경우
    else:
        length = 0
        found = 0
        # 꽂혀있는 전기용품을 찾아 다음 index가 가장 뒤에 있는 전기용품을 뽑기
        for i in range(1, 101):
            if concent[i]:
                found += 1
                if visit[i][concent[i]] > length:
                    length = visit[i][concent[i]]
                    getout = i
                if found == concent_max: break
        # 뽑은건 idx 0 으로 갱신, 꼽은것 idx 갱신
        concent[getout] = 0
        concent[now] = idx
        ans += 1
        return

다음은 현재 idx와 현재 전기용품을 입력받아 콘센트를 꼽을지, 뽑을지 결정하는 함수이다.

중요한건 뽑아야 하는 경우이니 해당 부분만 보자!

 

미리 현재 꽂혀있는 콘센트를 인덱스로 -> 해당 인덱스의 값을 꽃혀있는 위치로 지정해주었다.

따라서 콘센트 전체를 순회하며 꽃혀있다면 (0이 아니라면)

visit 배열에서 다음에 올 index값을 찾는다.

이후 가장 늦게 올 index의 값을 concent[getout] = 0으로 바꾸어주고

새로 꼽힌 콘센트 값에 idx값을 넣어준다.

 

위 함수를 전체 배열에 순회하며 문제를 해결했다.