[백준 / Python] 27278 영내순환버스

문제

 

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

27278번: 영내순환버스

---

Algorithm

 

운전병이 운전 업무를 마친 시간을 구하라고 했으므로 가장 마지막에 내린 병사가 언제내렸는지를 구하면 되는 문제이다.

문제에서 주어지는 거는 각 정류장 사이의 거리와 병사가 출발정거장에서 기다리기 시작한 시간이다.

그러면 우리가 따져주어야 하는 것은 다음과 같다.

1. 병사가 탑승한 시간
2. 병사가 내린 시간

을 고려해주면 된다.

1. 병사가 탑승한 시간

버스는 계속 순환하고, 문제에서 병사가 기다리기 시작한 시간이후에 버스가 도착하면 즉시 탑승한다고 했으므로, 해당 정거장에 버스가 언제 도착하는지 구하고 만약 해당 병사가 도착하기 전부터 기다렸다면 도착하자마자 탑승하고, 아니라면 버스가 한번 순환한 다음에 탑승해야하므로 그 다음 시간에 탑승하도록 설정해 주면 된다.

버스가 순환하므로 한 싸이클은 두번째 줄에 주어진 수들의 합이 된다. 

여기서 누적합을 사용할 수 있는데, 시각 0에 1번 정류장에서 출발하여 각 정거장을 들른후에 다시 1번정류장으로 오게 된다. 한 사이클을 20으로 예를 들어보면, 0 20 40 60 80 100 ... 이 시간에 1번정류장에서 탈 수 있고, 1번정류장과 2번 정류장 사이에 걸리는 시간이 4라고 하면 4 24 44 64 84 ... 이시간에 2번정류장에서 탈 수 있다.

두번째 줄에 주어진 수들의 누적합을 이용해 출발지점에서 제일 빨리 탑승할 수 있는 시간을 설정해준다. 우리가 세운 누적합은 각 정류장에서 탑승할 수 있는 시간이므로, 마지막정거장에서 1번정거장으로 갈때는 누적합을 계산하지 않는다.

 

cycle = sum(arr)    #버스가 한사이클 순환하는데 걸리는 시간
prefix = [0]    #누적합 배열
for i in range(1,n):    #누적합 계산
    prefix.append(prefix[i-1]+arr[i-1])
    
    ...
    
    time = prefix[p-1]  #출발지점에서 제일 빨리 출발할수 있는 시간
    if c%cycle > time:  #내가 기다리기 시작한 순간이 버스가 출발지점을 지나갔는지 그 전인지 판별한다.
        time += (c // cycle + 1) * cycle #버스가 지나간것이므로 한사이클을 기다려야함
    else:
        time += (c // cycle) * cycle

 

2. 병사가 내린 시간

병사가 내린 시간은 위에서 구한 탑승한 시각 + 버스에 탑승해 있는 시간이다. 버스에 탑승해 있는 시간은 정거장들 사이에 걸리는 시간이므로 간단하게 구할 수 있다.

2번 정거장에서 타서 5번 정거장에서 내린다고 하면 누적합배열에서 prefix[4] - prefix[0]을 해주면 되고, 4번정거장에서 타서 3번 정거장에 내린다고 하면, 한사이클에서 3번정거장에서 4번 정거장 사이에 걸리는 시간을 빼주면 된다.

    if p > r:   #이동하는데 걸리는 시간 계산
        time += prefix[r-1] + cycle - prefix[p-1]
    else:
        time += prefix[r-1] - prefix[p-1]

---

 

 

Code

input = __import__('sys').stdin.readline

n,m = map(int,input().split())
arr = list(map(int,input().split()))
cycle = sum(arr)    #버스가 한사이클 순환하는데 걸리는 시간
prefix = [0]    #누적합 배열
for i in range(1,n):    #누적합 계산
    prefix.append(prefix[i-1]+arr[i-1])
temp = []   #결과들 담을 배열
for i in range(m):
    p,r,c = map(int,input().split())    #출발지점, 도착지점, 기다리기 시작한 시간 입력
    time = prefix[p-1]  #출발지점에서 제일 빨리 출발할수 있는 시간
    if c%cycle > time:  #내가 기다리기 시작한 순간이 버스가 출발지점을 지나갔는지 그 전인지 판별한다.
        time += (c // cycle + 1) * cycle #버스가 지나간것이므로 한사이클을 기다려야함
    else:
        time += (c // cycle) * cycle    #버스가 지나가기 전이므로 현재 사이클에서 도착할 시간을 계산
    if p > r:   #이동하는데 걸리는 시간 계산
        time += prefix[r-1] + cycle - prefix[p-1]
    else:
        time += prefix[r-1] - prefix[p-1]
    temp.append(time)
print(max(temp))    #가장 늦는 시간, 최댓값 출력