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

10713번: 기차 여행

 

문제

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 (20점)

• 2 ≦ N ≦ 1 000.
• M = 2.
• 1 ≦ Bi < Ai ≦ 1 000 (1 ≦ i ≦ N − 1).
• 1 ≦ Ci ≦ 1 000 (1 ≦ i ≦ N − 1).

 

서브태스크 2 (30점)

• 2 ≦ N ≦ 1 000.
• 2 ≦ M ≦ 1 000.
• 1 ≦ Bi < Ai ≦ 1 000 (1 ≦ i ≦ N − 1).
• 1 ≦ Ci ≦ 1 000 (1 ≦ i ≦ N − 1).

 

서브태스크 3 (50점)

추가적인 제약 조건이 없다.

 

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
path = list(map(int, input().split()))
fee = [[] for _ in range(n)]
for i in range(1, n):
    fee[i] = list(map(int, input().split()))
# 철도 이용횟수 누적합
accum = [0] * (n+1)
for i in range(m-1):
    if path[i] < path[i+1]:
        accum[path[i]] += 1
        accum[path[i+1]] -= 1
    else:
        accum[path[i+1]] += 1
        accum[path[i]] -= 1
ans = 0
a = 0
for i in range(1, n):
    a += accum[i]
    ticket = fee[i][0] * a
    card = fee[i][2] + fee[i][1] * a
    ans += min(ticket, card)
print(ans)

i->i+1 마을로 가는 철도는 i번 철도이므로 1->3으로 갈 때 거치는 철도는 1, 2번 철도이다. 그러므로 누적합을 구하기 위한 배열인 accum의 값을 채워줄 때 이동경로를 2개씩 살펴보며 더 작은 숫자의 마을의 accum 값을 +1, 큰 숫자의 마을의 accum 값은 -1 해준다. 이렇게 해주면 나중에 누적합이 각 철도를 이용한 횟수가 된다.

각 철도를 이용한 횟수를 알았으니 티켓을 이용했을 때와 IC카드를 이용했을때의 총 요금을 구할 수 있다. 이 두 값 중 작은 값을 ans에 더해주면 된다.

 

 

처음에는 아래와 같이 브루트포스로 풀어서 50점이 나왔다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
path = list(map(int, input().split()))
fee = [[] for _ in range(n)]
for i in range(1, n):
    fee[i] = list(map(int, input().split()))
num = [0] * n
for i in range(m-1):
    for j in range(min(path[i], path[i+1]), max(path[i], path[i+1])):
        num[j] += 1
ans = 0
for i in range(1, n):
    ticket = fee[i][0] * num[i]
    card = fee[i][2] + fee[i][1] * num[i]
    ans += min(ticket, card)
print(ans)

서브태스크가 입력값별로 있는걸 보니 이렇게 하면 안되겠다는 생각이 들긴 했다. 1-N-1-N-...과 같이 반복하는 최악의 경우에는 시간복잡도가 O(NM)이기 때문에 모든 서브태스크 통과가 힘들 것이다. 그래도 혹시 몰라서 돌려보니 50점이었다.