[백준/구현] 1680번 쓰레기 수거

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

1680번: 쓰레기 수거

 

[풀이 방법]

 

쓰레기 차는 다음 3가지 경우일 때, 쓰레기장으로 돌아가 싣고 있는 쓰레기를 비운다.

 

1. 쓰레기의 양이 용량에 도달했을 때.

2. 그 지점의 쓰레기를 실었을 때 쓰레기차의 용량을 넘게 될 때.

3. 더 이상 쓰레기를 실을 지점이 없을 때.

 

주어진 거리는 지점과 쓰레기장의 거리고, 일직선상에 모든 지점이 있으므로

이전 지점의 거리를 기억해서 현재 지점의 거리와 뺀 것으로 이동 거리를 계산했다.

예를 들어, 거리는 1 지점 ~ 쓰레기 장 : 1, 2 지점 ~ 쓰레기 장 : 2 이면 1지점~2지점:1 이다.

 

지점에 들려서 쓰레기를 채울 때, 3가지 경우가 있다.

1. 쓰레기차에 해당 지점의 쓰레기를 채워도 용량보다 적을 경우

이 경우는, 해당 지점 - 이전 지점의 거리를 더하면 된다.

 

2. 채웠을 때 허용 용량과 같을 경우

이 경우는, 쓰레기 장으로 돌아가야하므로 해당 지점 - 이전 지점 거리를 더하고,

해당 지점과 쓰레기 장 사이의 거리의 2배를 더한다. (왔다갔다하므로)

이 때, 만약 해당 지점이 마지막이면 왔다갔다 하지 않고, 쓰레기 장만 가면 되므로

일단은 해당 지점 - 이전 지점 거리를 더한다.

 

3. 채웠을 때 허용 용량보다 클 경우

이 경우는, 쓰레기 장으로 돌아가서 버리고 다시 해당 지점으로 돌아와서 쓰레기를 채운다.

즉, 거리는 해당 지점 - 이전 지점 거리를 더하고, 해당 지점과 쓰레기 장 사이의 거리의 2배를 더한다.

이 때는 마지막이어도, 다시 와야하므로 다른 조건문을 달지 않는다.

 

이제 모든 쓰레기를 수거했다면, 그 지점에서부터 다시 쓰레기장으로 간다.

 

 

#Test 개수
for _ in range(int(input())):
    w,n = map(int,input().split())
    T = []
    for __ in range(n):
        x,wi = map(int,input().split())
        T.append((x,wi))


    car = 0
    dis = 0
    previous = 0

    for i in T:
        #i[0]:거리,i[1]:양
        if car + i[1]<w:
            dis+=i[0]-previous
            car +=i[1]
        elif car + i[1] == w:
            dis += (i[0]-previous)+ i[0]*2
            car = 0
            if T.index(i)==n-1:
                dis -= i[0]*2
        elif car + i[1] > w:
            car = i[1]
            dis += (i[0] - previous) + i[0] * 2
        previous = i[0]

    #모든 쓰레기 수거
    if T.index(i)==n-1:
        dis += i[0]

    print(dis)