[Algorithm🧬] 백준 8980 : 택배

문제

처음에 문제 테케만 생각하고 푼 것

마을을 하나씩 방문하면서 담을 수 있는거 다 담고 내릴 수 있는거 다 내리고

4 40
3
1 4 40
2 3 40
3 4 40

이런 케이스만 있어도 답이 제대로 안찍힘.
시작하는 마을 기준으로만 생각하면 안된다.

import sys

readl = sys.stdin.readline


n, c = map(int, readl().split())
m = int(readl())
post = [list(map(int, readl().split())) for _ in range(m)]

post.sort()


weight = 0
postman = []
res = 0
j = 0


for i in range(1, n + 1):
    내리는개수 = 0
    for _, 내릴곳, 무게 in postman:
        if i == 내릴곳:
            res += 무게
            weight -= 무게
            내리는개수 += 1
        else:
            break

    postman = postman[내리는개수:]
    postman.sort(key=lambda x: x[1])


    # print(postman, weight)

    while j < m and post[j][0] == i:
        s, e, w = post[j]
        j += 1
        if weight >= c:
            break

        if weight + w <= c:
            postman.append((s, e, w))
            weight += w
        else:
            postman.append((s, e, c - weight))
            weight += (c - weight)

    postman.sort(key=lambda x: x[1])
    # print(postman, weight)


print(res)

그래서 시작 기준으로 생각하면 안된다는 것까진 알았는데,
회의실 배정 문제처럼 순서를 구해서 할 수 있는 모든 순서를 구해볼까? 했는데 여기는 한번에 한팀만 회의를 할 수 있는게 아니라 무게만 되면 택배차에 여러개를 실을 수도 있어서 그걸 어떻게 고려해야할지 감이 안잡혔다.

결국 참고...

회의실 배정처럼 배정을 하는데, 무게에 대한 신경을 배열을 이용해서 써주는 방법이었다.

import sys

readl = sys.stdin.readline


n, c = map(int, readl().split())
m = int(readl())
post = [list(map(int, readl().split())) for _ in range(m)]

# # 어차피 c 보다 큰건 택배에 담을수도 없으니 줄여놓고 시작.
# post = list(map(lambda x: [int(x[0]), int(x[1]), int(x[2])] if int(x[2]) <= c else [int(x[0]), int(x[1]), c], post))
post.sort(key = lambda x:x[1])



res = 0
postman = [c] * (n + 1) # 마을별로 남아있는 무게

for s, e, w in post:
    min_left_weight = c
    # 짐이 해당 마을 구간 사이에서 계속 실려있을 수 있으려면
    # 남은 무게에서 가장 작은 만큼만 실을 수 있음.
    for i in range(s, e):
        min_left_weight = min(min_left_weight, postman[i])

    possible_weight = min(min_left_weight, w)
    for i in range(s, e):
        postman[i] -= possible_weight
    res += possible_weight

print(res)