백준 1516번 게임 개발, 1700번 멀티탭 스케줄링 (Python)

1516번 게임 개발

건물을 짓는 속도와 이전에 지어져야하는 건물들이 주어질 경우, 모든 건물을 짓는데 걸리는 시간을 구하는 문제입니다.

 

전형적으로 Dynamic Programming를 활용해 풀 수 있는 문제라고 생각했습니다.

dp에 저장할 값은 각 번호의 건물을 짓는데 걸리는 속도로 했습니다.

 

우선, 이전에 지어져야하는 건물이 없는 건물의 경우 자신만 지으면 되므로 건물을 짓는데 걸리는 시간을 dp에 저장했습니다.

그 이후 건물을 짓기 전 필요한 건물이 있을 경우 해당 건물들이 지어지는 속도를 우선 확인하도록 했습니다.

 

건물의 번호를 i라 할 때, dp[i]에 값이 존재한다면 그 값을 반환해주었고, 값이 없다면 해당 건물을 지을 때 필요한 시간을 측정해줍니다.

dp[i]의 값은 (필요한 건물들의 건설 시간+자신의 건물을 짓는 시간)입니다.

필요한 건물들을 건설하는 시간은 필요한 건물들의 건설 시간 중 최대값입니다. 문제에서 여러 개의 건물을 동시에 지을 수 있다고 했으므로 필요한 건물들을 동시에 지어서 모든 건물이 완성 된다면 i 건물을 지을 수 있기 때문입니다.

그러므로 필요한 건물들의 건설 시간 중 최대값과 해당 건물을 짓는 시간을 더한 값이 해당 건물을 짓는데 필요한 총 시간입니다.

 

전체 코드

def recursion(num):
    if dp[num] != 0:
        return dp[num]

    temp = 0
    for i in range(1, len(components[num])):
        temp = max(temp, recursion(components[num][i]-1))
    dp[num] = temp+components[num][0]
    return dp[num]


N = int(input())
components = [list(map(int, input().split()[:-1])) for _ in range(N)]
dp = [0 for _ in range(N)]

for i in range(N):
    if len(components[i]) == 1:
        dp[i] = components[i][0]

for i in range(N):
    print(recursion(i))

 

 

1700번 멀티탭 스케줄링

N개의 구멍을 가진 멀티탭에 K번 전기용품을 번갈아가면서 사용할 때 전기 용품을 사용하는 순서를 알고 있다면, 플러그를 빼는 횟수의 최소값을 구하는 문제입니다.

 

1️⃣ 아이디어 1.

전기 용품이 나오는 빈도수를 구하고 멀티탭에 꽂혀있는 것 중 빈도수가 가장 적은 물품부터 뺀다면 플러그를 빼는 횟수를 최소화할 수 있다고 생각했습니다.

하지만, 빈도수만으로는 최소값을 항상 구할 수 없었습니다.

 

예시. 

멀티탭의 구멍이 2개이고 순서가 1 2 3 4 3 4 2 2 인 경우

멀티탭 : [ 1, 2 ]

멀티탭 : [ 3, 2 ]

멀티탭 : [ 2, 3 ]

멀티탭 : [ 2, 4 ]

멀티탭 : [ 2, 3 ]

멀티탭 : [ 2, 4 ]

...

그러므로 플러그를 빼는 횟수는 5번이 됩니다. 하지만, 실제로는 3번만 빼면 됩니다.

 

그러므로 빈도수보다는 나타나는 순서를 우선순위로 하도록 했습니다.

 

2️⃣ 아이디어 2.

멀티탭에 꽂혀있는 전기 용품 중 다시 사용하게 되는 순서가 가장 멀리 있는 것부터 멀티탭에서 제거하도록 했습니다.

이렇게 한다면 다시 사용하는 순서가 가까운 전기용품일수록 많이 살아남게 되므로, 좀 더 플러그를 빼는 횟수를 줄일 수 있다고 생각했습니다.

 

그래서, 현재 플러그가 꽉찼다면 플러그에 꽂혀 있는 전기용품들의 재등장 순서를 확인하고 가장 멀리 있는 것을 멀티탭에서 먼저 제거해주도록 했습니다.

 

전체 코드

from queue import PriorityQueue
from collections import defaultdict

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

if N >= K:
    print(0)
    exit()

multitab = set()
answer = 0

for i, thing in enumerate(things):
    multitab.add(thing)
    if len(multitab) <= N:
        continue

    answer += 1

    later_used = 0
    later_idx = -1
    for plug in multitab:
        try:
            index = things[i:].index(plug)
        except:
            index = K

        if later_idx < index:
            later_used = plug
            later_idx = index

    multitab.discard(later_used)

print(answer)

당연히, 멀티탭 구멍 개수가 전기용품의 개수보다 크다면 플러그를 뺄 필요가 없으므로 0을 출력해주었습니다.