[백준] 2170, 1700, 8980 (파이썬)

그리디 알고리즘 문제집은 다음 날짜로 종료될 것 같다. 하지만 모자람이 아직 느껴지기에 문제집 하나를 추가할 예정이다. 프로젝트로 인해서 시간이 모자라지만 습관을 위해서 꾸준히 풀어보고자 한다.

백준 2170번 선 긋기

import sys
T = int(sys.stdin.readline())
num_lst = list()
for _ in range(T):
    num_lst.append(list(map(int,sys.stdin.readline().split())))
num_lst = sorted(num_lst,key=lambda x:(x[0],x[1]))
min_num = num_lst[0][0]
max_num = num_lst[0][1]
count = 0
for i in range(1,T):
    if max_num < num_lst[i][0] :
        count += (max_num-min_num)
        min_num = num_lst[i][0]
        max_num = num_lst[i][1]
    elif max_num < num_lst[i][1] :
        max_num = num_lst[i][1]
count += (max_num-min_num)
print(count)

백준 1700번 멀티탭 스케줄링

import sys
N,K = map(int,sys.stdin.readline().split())
multitap = list(map(int,sys.stdin.readline().split()))
plug = list()
count = 0
for i in range(K):
    # 이미 플러그에 있는 경우
    if multitap[i] in plug:
        continue
    # 플러그가 비어있는 경우
    if len(plug) < N:
        plug.append(multitap[i])
        continue
    # 플러그를 뽑아야하는 경우
    idx_lst = list()
    for j in range(N):
        # 플러그 꽂혀있는 전기용품이 이후에도 사용 O
        if plug[j] in multitap[i:]:
            idx = multitap[i:].index(plug[j])
        else:
            idx = 101
        # 플러그 꽂혀있는 전기용품이 이후에도 사용 X
        idx_lst.append(idx)
    # 사용 X or 가장 멀리 있는 index 지는 plug 제거
    plug_out = idx_lst.index(max(idx_lst))
    del plug[plug_out]
    plug.append(multitap[i])
    count +=1
print(count)

백준 8980번 택배

# 생각보다 어려웠던 문제, 알고리즘을 참고하여 풀었다.
import sys
N,C = map(int,sys.stdin.readline().split())
M = int(sys.stdin.readline())
opt = list()
for _ in range(M):
    opt.append(list(map(int,sys.stdin.readline().split())))
# 도착위치 중심 정렬
opt.sort(key=lambda x:x[1])
count = 0
# 각 위치에 남은 공간
locate = [C]*(N+1)  
for start,end,box in opt:
    min_box = C
    for i in range(start, end):
        min_box = min(min_box, locate[i])
    min_box = min(min_box, box)
    for i in range(start, end):
        locate[i] -= min_box
    count += min_box
print(count)