[백준 10713번] 파이썬 - 기차 여행

백준 10713 - 기차 여행

시간 제한 1초, 메모리 제한 256MB

# 조건

• JOI나라에는 N개의 도시가 있고, 각 도시에 1,2,...,N까지의 번호를 갖고 있다.
• 그리고, 철도가 N-1개 있고, 각 철도에 1,2,...N-1의 번호를 갖고 있다.
• 철도 i (1 ≦ i ≦ N − 1)는 도시 i과 도시 i+1을 양방향으로 연결시키는 철도를 의미한다.
• JOI나라의 철도를 타는 방법에는, 티켓을 구입해 승차하는 방법과 IC카드로 승차하는 방법 두 가지가 존재한다.
  • 철도 i에 티켓을 구입해 승차할 때는 Ai 원의 비용이 든다.
  • 철도 i에 IC카드로 승차하는 경우에는 Bi 원의 비용이 든다.
  • 하지만 IC카드로 철도를 탈 때는 IC카드를 미리 구입해둬야만 한다.
  • 철도 i에서 쓸 수 있는 IC카드를 구입하는데는 Ci원의 비용이 든다.
  • 한번 구입한 IC카드는 몇번이라도 사용할 수 있다.
• IC카드가 처리가 간편하기 때문에, IC카드로 승차하는 방법의 운임이 티켓을 구입하는 경우보다 싸다.
  • 즉, i = 1,2,...N-1일 때 Ai > Bi이다.
  • IC카드는 철도마다 다르기 때문에, 철도 i에서 사용할 수 있는 카드는 다른 철도에서는 사용할 수 없다.
• 당신은 JOI나라를 여행하기로 마음먹었다.
  • 도시 P1에서 출발해, P2,P3... ,PM 순서의 도시를 방문할 예정이다.
  • 여행은 M-1일간 이루어진다.
  • j일째 (1 ≦ j ≦ M − 1) 에 도시 Pj으로부터 Pj+1으로 이동한다.
  • 이때, 여러 개의 철도를 타는 경우도 있고, 같은 도시를 여러 번 방문할 수도 있다.
  • JOI나라의 철도는 빨라서 어느 도시도 하루만에 도착할 수 있다
• 당신은 현재 어느 철도의 IC카드도 갖고있지 않다.
  • 당신은 미리 몇개의 IC카드를 구입해, 이 여행에서 사용되는 비용, 즉 IC카드를 구입하는 비용 + 철도를 타는 비용을 최소화하고 싶다.
• JOI나라의 도시 수, 여행의 기간, 그리고 JOI나라의 철도 각각의 운임과, IC카드의 가격이 주어졌을 때, 여행의 비용을 최소화하는 프로그램을 작성하시오.

입력

• 첫 번째 줄에서는 정수 N, M이 주어진다.
• 두 번째 줄에는 M개의 정수 P1,P2,...PM이 주어진다.
• j일째 (1 ≦ j ≦ M − 1) 에 도시 Pj에서 Pj+1로 이동하는 것을 의미한다.
• 3번째 줄부터 N-1개의 줄에는 (1 ≦ i ≦ N − 1) 3개의 정수 Ai, Bi, Ci가 주어진다.
• 각각 철도 i의 티켓을 구입하는 가격, 철도 i를 카드를 사용했을 때 통과하는 가격, IC카드를 구매하는 가격을 의미한다.

출력

• 여행에 드는 최저 비용을 첫째 줄에 출력하시오.

# 제한

• 2 ≦ N ≦ 100 000．
• 2 ≦ M ≦ 100 000．
• 1 ≦ Bi < Ai ≦ 100 000 (1 ≦ i ≦ N − 1)．
• 1 ≦ Ci ≦ 100 000 (1 ≦ i ≦ N − 1)．
• 1 ≦ Pj ≦ N (1 ≦ j ≦ M)．
• Pj ≠ Pj+1 (1 ≦ j ≦ M − 1)．

# 접근 방법

• 이동 경로 중 거치는 모든 기차역을 하나씩 카운트 해주면 시간 초과가 발생한다.
• 따라서, 출발역과 도착역에 +1, -1을 해준 후 누적 합을 이용하여 모든 기차역의 사용 횟수를 구해주는 것이 핵심이다.
  • 이 때, 2 -> 3으로 가는 것과 3 -> 2로 가는 것은 동일하기 때문에 번호가 작은 기차역에 +1을 해준다.
• 이후, 각 기차역마다 티켓을 사용하는 것 vs ic카드 구매 후 이용하는 것을 비교해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, M = map(int, input().split())  
route = list(map(int, input().split()))  
info = [[0, 0, 0] for _  in range(N+1)]  
for i in range(1, N):  
    a, b, c = map(int, input().split())  
    info[i] = [a, b, c]  
# 각 철도별 이용횟수  
count = [0] * (N+1)  
for i in range(M-1):  
    if route[i] < route[i+1]:  
        count[route[i]] += 1  
        count[route[i+1]] -= 1  
    else:  
        count[route[i+1]] += 1  
        count[route[i]] -= 1  

sum = 0  
result = 0  

# 누적합으로 각 철도별 실제 사용횟수 구한 뒤 ic vs 티켓  
for i in range(1, N):  
    sum += count[i]  
    result += min(info[i][0] * sum, info[i][1] * sum + info[i][2])  
print(result)