백준.멀티탭 스캐줄링.1700.py

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

1700번: 멀티탭 스케줄링

완전탐색으로 풀다가 => 시간초과 +메모리초과 => 그래도 나와있는 테케중엔 틀린거x

그리디로 다시 도전

성공

그리디 코드

# 교훈: 멀티탭을 사자
import sys
def solution(start_set, procedures,n):
    case_set, pro_dic, case_cnt = start_set, dict(),0
    
    for idx, pr in enumerate(procedures):
        if pr in pro_dic:
            pro_dic[pr].append(idx)
        else:
            pro_dic[pr] = [idx]

    for pr in procedures:
        if pr in case_set:
            del pro_dic[pr][0]
        else:
            case_cnt += 1
            del pro_dic[pr][0]
            # case_set 중에 안나오는거 제거, 만약 다 나오면
            # case_set 중에 가장 나중에 나오는 제품을 제거
            later_idx, later_prod = [], False
            for product in case_set:
                if len(pro_dic.get(product,[])) == 0:
                    later_prod = product
                    break
                else:
                    later_idx.append(min(pro_dic[product]))
            if later_prod:
                case_set.remove(later_prod)
            else:
                case_set.remove(procedures[max(later_idx)])
            case_set.add(pr)
            
    return case_cnt

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().rstrip().split())
    use_procedure = list(map(int, sys.stdin.readline().rstrip().split()))
    start_pro = set()
    cnt = 0
    while True:
        cnt += 1
        start_pro.add(use_procedure[0])
        del use_procedure[0]
        if len(start_pro) == n or len(use_procedure) == 0: break

    if k-cnt+n <= n:
        print(0)
    else:
        min_cnt = solution(start_pro,use_procedure,n)
        print(min_cnt)

완전탐색 코드

# 교훈: 멀티탭을 사자
import sys
def solution(start_set, procedures,n):
    case_set_list, case_cnt = [start_set], [0]
    min_cnt = 200
    for pr in procedures:
        new_case_set_list = []
        new_case_cnt = []
        for i, case_set in enumerate(case_set_list):
            if pr in case_set:
                new_case_set_list.append(case_set)
                new_case_cnt.append(case_cnt[i])
            else:
                for num in case_set:
                    if min_cnt+n > case_cnt[i]+1:
                        new_case_set_list.append({pr} | case_set - {num})
                        new_case_cnt.append(case_cnt[i]+1)

        min_cnt = min(new_case_cnt)
        case_set_list = new_case_set_list
        case_cnt = new_case_cnt

    return min(case_cnt)

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().rstrip().split())
    use_procedure = list(map(int, sys.stdin.readline().rstrip().split()))
    if k <= n:
        print(0)
    else:
        min_cnt = solution(set(use_procedure[0:n]),use_procedure[n:k],n)
        print(min_cnt)