[알고리즘] 탐욕법 - 스케쥴링 코드 (Greedy Approach - Scheduling Code)

문제)

Description

교재와 강의자료를 참고하여 Algorithm 4.4 Scheduling with Deadlines 의 구현을 완성하시오.

입력값은 profit의 내림차순으로 이미 정렬이 되어 있다고 가정해도 된다.

출력은 최대 이익과 함께 feasible sequence의 profit을 순서대로 출력한다.

Input

첫째 줄에 job의 개수 n이 주어진다.

둘째 줄에 n개의 deadline이 주어진다.

셋째 줄에 n개의 profit이 주어진다.

단, profit은 내림차순으로 정렬되어 있다.

Output

첫 줄에 최대 이익의 값을 출력한다.

둘째 줄에 Algorithm 4.4가 발견한 job sequence의 순서대로 각 job의 profit을 출력한다.

Sample Input 1

7
3 1 1 3 1 3 2
40 35 30 25 20 15 10

Sample Output 1

100
35 40 25

Sample Input 2

5
2 1 2 1 3
97 27 25 19 13

Sample Output 2

137
27 97 13

코드)

import sys
import copy
input = sys.stdin.readline


def is_feasible(J):
    # 해당 set이 feasible한지 확인하는 함수
    len_J = len(J)      # len(J)를 계속 호출하는 것보다 변수에 저장하는게 나음

    for i in range(1, len_J):
        # 해당 set이 feasible한지 확인함
        if J[i][0] < i:     # i번째에 위치한 job의 데드라인이 i보다 작다면 false임
            # i번째에 위치했다는 뜻은 해당 job이 끝나는 시간이 i라는 뜻임
            return False
    return True


def func():
    # scheduling 하는 함수
    S = []      # feasible set임
    S.append(job_dict[0])        # 먼저 0을 넣어서 편리하게 이용함
    S.append(job_dict[1])

    J = []      # 쓰레기 집합

    for i in range(2, n + 1):
        J = copy.deepcopy(S)        # J가 S를 복사함

        idx = 1     # 새로운 작업이 들어갈 곳
        k = job_dict[i][0]      # 새로운 작업의 데드라인
        while idx < len(J) and J[idx][0] <= k:
            # 새로운 작업이 어디에 들어가야할지 정함, 데드라인을 기준으로 오름차순을 하면 됨
            # idx가 J의 길이를 넘지 않아야 하고, 앞의 idx의 deadline의 새로운 작업의 deadline보다 작아야함
            idx += 1

        J.insert(idx, job_dict[i])      # job이 있어야 하는 자리에 넣음

        if is_feasible(J):      # 만약 J가 수행가능하다면 S에 집어 넣음
            S.insert(idx, job_dict[i])
    
    return S


n = int(input())        # job의 개수
deadline = list(map(int, input().split()))      # deadline을 받음
profit = list(map(int, input().split()))     # profit을 받음, profit은 내림차순으로 정렬되어 있음

job_dict = {0 : (0, 0)}
for i in range(1, n + 1):
    job_dict[i] = (deadline[i - 1], profit[i - 1])      # deadline과 profit의 집합을 만듬

# print(job_dict)
S = func()
print(sum([S[i][1] for i in range(1, len(S))]))     # 최대 profit을 출력
print(*[S[i][1] for i in range(1, len(S))], sep=' ')        # feasible sequence를 출력

 

코드2)

def is_feasible(K):
    # 실행 가능한지 체크하는 함수
    for i in range(len(K)):
        if i + 1 > deadline[K[i]]:
            # 해당 job의 데드라인이 i + 1보다 작으면 impossible한 것. 데드라인은 1부터 시작, i는 0부터 시작
            return False
    return True


def schedule(J):
    # 스케쥴링하는 함수
    for i in range(n):
        K = J.copy()  # 우선 복사함

        idx = 0     # K의 뒤에 새롭게 들어가야하는 위치를 정함

        while idx < len(K) and deadline[K[idx]] <= deadline[i]:
            # 우선 idx는 K의 길이보다 작아야하고,
            # K의 idx번째에 있는 애의 deadline은 i의 deadline보다 작아야함
            # 참고로 K에는 몇 번째 job이 들어가있는지를 나타냄, 1 0 3 이라면 두 번째, 첫 번째, 네 번째 작업이 들어가있는 것
            idx += 1

        K.insert(idx, i)        # deadline의 오름차순에 맞게 넣음
        if is_feasible(K):
            # 만약에 K가 실행 가능하다면
            J = K.copy()        # 그대로 J에 K를 카피함

    return J


n = int(input())        # 몇 개인지
deadline = list(map(int, input().split()))      # 데드라인
profit = list(map(int, input().split()))        # 이익

J = []      # 초기의 실행 가능 집합
J = schedule(J)

# 아래는 출력
feasible_total = list(map(lambda x: profit[x], J))
print(sum(feasible_total))
print(*feasible_total, sep=' ')